LeetCode 934. Shortest Bridge

934. Shortest Bridge

题解

题目是求两个连通块的最短路径，可以用宽搜。
宽搜有几个要注意的地方，1. 如何区分不同的连通块，2. 不要重复搜索。
在遍历的时候，首先找到第一个连通块，使用flood fill算法，把对应的连通块染色。然后再flood fill的同时，找到边缘的所有点，加入队列，之后在队列中，进行宽搜找到最短距离。
另外宽搜的时候，可以用距离数组维护是否需要加入队列中，不需要hash表。

代码

• 由于是宽搜，距离数组更新的时候必然是第一次遍历的时候，因此不会重复遍历。

  class Solution {
  public:
    int n, m;
    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {1, 0, -1, 0};
    typedef pair<int, int> PII;
    vector<vector<int>> dist;
    queue<PII> q;
    void flood_fill(vector<vector<int>>& grid, int x, int y) {
        grid[x][y] = -1;
        dist[x][y] = 0;
        q.push({x, y});
        for (int i = 0; i < 4; i ++) {
            int a = x + dx[i];
            int b = y + dy[i];
            if (a >= 0 && a < n && b >= 0 && b < m && grid[a][b] == 1) {
                flood_fill(grid, a, b);
            }
        }
    }
    int get_shortest_bridge(vector<vector<int>>& grid, int x, int y) {
        flood_fill(grid, x, y);
        while(q.size()) {
            int k = q.size();
            for (int i = 0; i < k; i ++) {
                auto p = q.front();
                q.pop();
                int x = p.first, y = p.second;
                // cout << x <<", " << y <<endl;
                for (int j = 0; j < 4; j ++) {
                    int a = x + dx[j];
                    int b = y + dy[j];
                    // cout << "(" << a << ", " << b << ")" << endl;
                    if (a >= 0 && a < n && b >= 0 && b < m && dist[a][b] > dist[x][y] + 1) {
                        dist[a][b] = dist[x][y] + 1;
                        q.push({a, b});
                    }
                    if (a >= 0 && a < n && b >= 0 && b < m && grid[a][b] == 1) {
                        return dist[a][b] - 1;
                    }
                }
            }
        }
        return -1;
    }
    int shortestBridge(vector<vector<int>>& grid) {
        n = grid.size(), m = grid[0].size();
        dist = vector<vector<int>>(n, vector<int>(m, 1e8));
        for(int i = 0; i < n; i ++) {
            for (int j = 0; j < m; j ++) {
                if (grid[i][j] == 1) {
                    return get_shortest_bridge(grid, i, j);
                }
            }
        }
        return -1;
    }
  };