934. Shortest Bridge.md

934. Shortest Bridge

https://leetcode.com/problems/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

代码

• BFS + DFS

class Solution {
    public int shortestBridge(int[][] A) {
        int rows = A.length, cols = A[0].length;
        Queue<int[]> q = new LinkedList<>();
        boolean found = false;
        for (int i = 0; i < A.length && !found; ++i) {
            for (int j = 0; j < A[0].length && !found; ++j) {
                if (A[i][j] != 0) {
                    dfs(A, i, j, q);
                    found = true;
                }
            }
        }
        int steps = 0;
        int[] dirs = {0, 1, 0, -1, 0};
        while (!q.isEmpty()) {
            int size = q.size();
            while (size-- != 0) {
                int x = q.peek()[0];
                int y = q.peek()[1];
                q.poll();
                for (int i = 0; i < 4; ++i) {
                    int tx = x + dirs[i];
                    int ty = y + dirs[i+1];
                    if (tx < 0 || ty < 0 || tx >= rows || ty >= cols || A[tx][ty] == 2)
                        continue;
                    if (A[tx][ty] == 1)
                        return steps;
                    A[tx][ty] = 2;
                    q.offer(new int[]{tx, ty});
                }
            }
            // end one step
            ++steps;
        }
        return -1;
    }

    private void dfs(int[][] A, int x, int y, Queue<int[]> q) {
        if (x < 0 || y < 0 || x >= A.length || y >= A[0].length || A[x][y] != 1)
            return;
        A[x][y] = 2;
        q.offer(new int[] {x,y});
        dfs(A, x-1, y, q);
        dfs(A, x+1, y, q);
        dfs(A, x, y-1, q);
        dfs(A, x, y+1, q);
    }
}