Shortest Bridge

In a given 2D binary array A, there are two islands. (An island is a 4-directionally connected group of 1s not connected to any other 1s.)

Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.

Return the smallest number of 0s that must be flipped. (It is guaranteed that the answer is at least 1.)

Example 1:

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

Example 2:

Input: A = [[0,1,0],[0,0,0],[0,0,1]]
Output: 2

Example 3:

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

Constraints:

• 2 <= A.length == A[0].length <= 100

• A[i][j] == 0 or A[i][j] == 1

class Solution {
    public void DFS(int[][] A, boolean[][] visited, Queue<int[]> q, int i, int j, int[][] dirs) {
        if (i < 0 || j < 0 || i >= A.length || j >= A[0].length || visited[i][j] || A[i][j] == 0)
            return;
        visited[i][j] = true;
        q.add(new int[] { i, j });
        for (int[] dir : dirs)
            DFS(A, visited, q, i + dir[0], j + dir[1], dirs);
    }

    public int shortestBridge(int[][] A) {
        int m = A.length, n = A[0].length;
        boolean[][] visited = new boolean[m][n];
        int[][] dirs = new int[][] { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        Queue<int[]> q = new LinkedList<>();
        boolean found = false;
        // 1. DFS to find an island, mark it in `visited`
        // Marking only one island
        for (int i = 0; i < m; i++) {
            if (found)
                break;
            for (int j = 0; j < n; j++) {
                if (A[i][j] == 1) {
                    DFS(A, visited, q, i, j, dirs);
                    found = true;
                    break;
                }
            }
        }
        // 2. BFS to expand this island
        // BFS from every point of marked island
        int step = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            while (size-- > 0) {
                int[] cur = q.poll();
                for (int[] dir : dirs) {
                    int i = cur[0] + dir[0];
                    int j = cur[1] + dir[1];
                    if (i >= 0 && j >= 0 && i < m && j < n && !visited[i][j]) {
                        if (A[i][j] == 1)
                            return step;
                        q.add(new int[] { i, j });
                        visited[i][j] = true;
                    }
                }
            }
            step++;
        }
        return -1;
    }
}