934 Shortest Bridge

934. Shortest Bridge

1. Question

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

Now, we may change0s to1s so as to connect the two islands together to form 1 island.

Return the smallest number of0s 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] == 0orA[i][j] == 1

2. Implementation

(1) DFS + BFS

思路:

• 先用DFS找到一个island

• 然后用BFS将找到的island expand，直至到达另一个island

class Solution {
    public int shortestBridge(int[][] A) {
        int m = A.length, n = A[0].length;
        Queue<int[]> queue = new LinkedList();
        boolean[][] visited = new boolean[m][n];
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        boolean found = false;

        for (int i = 0; i < m && !found; i++) {
            for (int j = 0; j < n && !found; j++) {
                if (A[i][j] == 1) {
                    findIslandByDFS(i, j, queue, visited, directions, A);
                    found = true;
                    break;
                }
            }
        }

        int step = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                int[] cur = queue.remove();

                for (int[] direction : directions) {
                    int nextRow = cur[0] + direction[0];
                    int nextCol = cur[1] + direction[1];

                    if (nextRow >= 0 && nextCol >= 0 && nextRow < m && nextCol < n && !visited[nextRow][nextCol]) {
                        if (A[nextRow][nextCol] == 1) {
                            return step;
                        }
                        queue.add(new int[] {nextRow, nextCol});
                        visited[nextRow][nextCol] = true;
                    }
                }
            }
            ++step;
        }
        return step;
    }

    public void findIslandByDFS(int row, int col, Queue<int[]> queue, boolean[][] visited, int[][] directions, int[][] A) {
        if (row < 0 || col < 0 || row >= A.length || col >= A[0].length || A[row][col] == 0 || visited[row][col]) {
            return;
        }

        visited[row][col] = true;
        queue.add(new int[] {row, col});

        for (int[] direction : directions) {
            int nextRow = row + direction[0];
            int nextCol = col + direction[1];
            findIslandByDFS(nextRow, nextCol, queue, visited, directions, A);
        }
    }
}

3. Time & Space Complexity

时间复杂度O(mn), 空间复杂度O(mn)