Задача: 934. Shortest Bridge
Сложность: medium

Вам дана двоичная матричная сетка n x n, где 1 обозначает сушу, а 0 - воду. Остров - это 4-направленно связанная группа из 1, не соединенная ни с одной другой 1. В сетке ровно два острова. Вы можете поменять 0 на 1, чтобы соединить два острова в один. Верните наименьшее количество 0, которое нужно перевернуть, чтобы соединить два острова.

Пример:

Input: grid = [[0,1],[1,0]]
Output: 1

👨‍💻 Алгоритм:

1⃣Найти все клетки, принадлежащие первому острову, используя DFS/BFS, и добавить их в очередь для последующего расширения.

2⃣Использовать BFS для расширения из каждой клетки первого острова, чтобы найти кратчайший путь к клетке второго острова.

3⃣Вернуть длину кратчайшего пути.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int ShortestBridge(int[][] grid) {
        int n = grid.Length;
        var directions = new int[][] {
            new int[] {-1, 0},
            new int[] {1, 0},
            new int[] {0, -1},
            new int[] {0, 1}
        };
        
        var queue = new Queue<int[]>();
        bool found = false;
        
        for (int i = 0; i < n && !found; ++i) {
            for (int j = 0; j < n && !found; ++j) {
                if (grid[i][j] == 1) {
                    Dfs(grid, i, j, queue);
                    found = true;
                }
            }
        }
        
        int steps = 0;
        while (queue.Count > 0) {
            int size = queue.Count;
            for (int i = 0; i < size; ++i) {
                var point = queue.Dequeue();
                int x = point[0], y = point[1];
                foreach (var dir in directions) {
                    int nx = x + dir[0], ny = y + dir[1];
                    if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                        if (grid[nx][ny] == 1) {
                            return steps;
                        }
                        if (grid[nx][ny] == 0) {
                            grid[nx][ny] = -1;
                            queue.Enqueue(new int[] {nx, ny});
                        }
                    }
                }
            }
            steps++;
        }
        
        return -1;
    }
    
    private void Dfs(int[][] grid, int x, int y, Queue<int[]> queue) {
        int n = grid.Length;
        if (x < 0 || x >= n || y < 0 || y >= n || grid[x][y] != 1) {
            return;
        }
        grid[x][y] = -1;
        queue.Enqueue(new int[] {x, y});
        Dfs(grid, x - 1, y, queue);
        Dfs(grid, x + 1, y, queue);
        Dfs(grid, x, y - 1, queue);
        Dfs(grid, x, y + 1, queue);
    }
}

Ставь 👍 и забирай 📚 Базу знаний