934. Shortest Bridge

934. 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: [[0,1],[1,0]]
Output: 1

Example 2:

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

Example 3:

Input: [[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

Note:

1. 1 <= A.length = A[0].length <= 100
2. A[i][j] == 0 or A[i][j] == 1

-------------------
BFS
先标记出一个岛，然后做BFS直到碰到另一个岛
注意dis的初始值是 -1

class Solution {
    public int shortestBridge(int[][] arr) {

        Queue<int[]> que = new LinkedList<>();

        for (int i = 0; i < arr.length; i++) {
            boolean f = false;
            for (int j = 0; j < arr[0].length; j++) {
                if (arr[i][j] == 1) {
                    dfs(arr, i, j, que);
                    f = true;
                    break;
                }
            }
            if (f) break;
        }

        int dis = -1;
        while (!que.isEmpty()) {
            
            for (int size = que.size(); size > 0; size--) {
                int[] top = que.poll();
                int i = top[0], j = top[1];
                if (i < 0 || j < 0 || i >= arr.length || j >= arr[0].length || arr[i][j] == 3) continue;
                if (arr[i][j] == 1) return dis;
                arr[i][j] = 3;
                que.add(new int[]{i + 1, j});
                que.add(new int[]{i, j + 1});
                que.add(new int[]{i - 1, j});
                que.add(new int[]{i, j - 1});
            }
            dis++;
        }


        return 0;
    }

    private void dfs(int[][] arr, int i, int j, Queue<int[]> que) {
        if (i < 0 || j < 0 || i >= arr.length || j >= arr[0].length || arr[i][j] == 0 || arr[i][j] == 2) return;

        arr[i][j] = 2;
        que.add(new int[]{i, j});
        dfs(arr, i + 1, j, que);
        dfs(arr, i - 1, j, que);
        dfs(arr, i, j + 1, que);
        dfs(arr, i, j - 1, que);
    }
}