Leetcode 934. Shortest Bridge

[Woodyiiiiiii]

Leetcode 934. Shortest Bridge

934. Shortest Bridge

这道题很显然就直接用DFS/BFS来做，但问题是数组长度是100 * 100，显然为了保证时间复杂度要小于O(10^8)，最好对每个节点只访问一次，所以要利用访问数组。

思考步骤：

1. 既然已经明确图中有两个island，那么自然想到从一个岛屿出发，BFS一层层到另一个岛屿
2. 那么首先要将第一个岛屿识别出来，并标记，可以用DFS/BFS(我还想过单纯用左右上下判断，太单纯了)

我卡了很久的一个点是岛屿扩散BFS一直TLE，百思不得其解，明明用了访问数组，这里有个细节，访问标记代码的位置要放在访问四个方向验证过后，这样保证了队列中就不会有重复结点了，代码如下：

v[x][y] = true;                 // 不是在这里
for (int[] dir : dirs) {
        int x = dir[0] + cur[0], y = dir[1] + cur[1];
         
         if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || v[x][y]) {
                continue;
          }
          if (grid[x][y] == 1) {
                return step;
           }
           v[x][y] = true;                 // 在这里
           q.add(new int[]{x,y});
}

class Solution {

    final int[][] dirs = new int[][]{{-1,0},{0,1},{1,0},{0,-1}};
    int n;
    Queue<int[]> q = new LinkedList<>();

    public int shortestBridge(int[][] grid) {
        n = grid.length;
        boolean[][] v = new boolean[n][n];
        boolean found = false;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    continue;
                }
                dfs(i, j, v, grid);
                found = true;
                break;
            }
            if (found) {
                break;
            }
        }

        int step = 0;
        while (!q.isEmpty()) {
            int sz = q.size();
            while (sz-- > 0) {
                int[] cur = q.poll();
                for (int[] dir : dirs) {
                    int x = dir[0] + cur[0], y = dir[1] + cur[1];
                    if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || v[x][y]) {
                        continue;
                    }
                    if (grid[x][y] == 1) {
                        return step;
                    }
                    v[x][y] = true;
                    q.add(new int[]{x,y});
                }
            }
            step++;
        }

        return -1;
    }

    private void dfs(int i, int j, boolean[][] v, int[][] grid) {
        v[i][j] = true;
        q.add(new int[]{i, j});
        for (int[] dir : dirs) {
            int x = dir[0] + i, y = dir[1] + j;
            if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || v[x][y] || grid[x][y] == 0) {
                continue;
            }
            q.add(new int[]{x, y});
            v[x][y] = true; 
            dfs(x, y, v, grid);
        }
    }

}