934.最短的桥

链接：934.最短的桥
难度：Medium
标签：深度优先搜索、广度优先搜索、数组、矩阵
简介：返回必须翻转的 0 的最小数目。

题解 1 - cpp

• 编辑时间：2022-10-25
• 执行用时：44ms
• 内存消耗：18.6MB
• 编程语言：cpp
• 解法介绍：bfs。

typedef pair<int, int> node;
const int dirs[4][2] = {
    {0, 1}, {0, -1},
    {1, 0}, {-1, 0}
};
class Solution {
public:
    int shortestBridge(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<bool>> check(n, vector<bool>(n, false));
        queue<node> q;
        int f = true;
        for (int i = 0; i < n && f; i++) {
            for (int j = 0; j < n && f; j++) {
                if (grid[i][j] == 1) {
                    queue<node> tmp;
                    tmp.push(make_pair(i, j));
                    check[i][j] = true;
                    while (tmp.size()) {
                        node v = tmp.front();
                        tmp.pop();
                        q.push(make_pair(v.first, v.second));
                        for (int k = 0; k < 4; k++) {
                            int ni = v.first + dirs[k][0], nj = v.second + dirs[k][1];
                            if (ni < 0 || ni == n || nj < 0 || nj == n || grid[ni][nj] == 0 || check[ni][nj]) continue;
                            tmp.push(make_pair(ni, nj));
                            check[ni][nj] = true;
                        }
                    }
                    f = false;
                }
            }
        }
        int level = 1, size = q.size();
        while (q.size()) {
            node v = q.front();
            q.pop();
            for (int i = 0; i < 4; i++) {
                int ni = v.first + dirs[i][0], nj = v.second + dirs[i][1];
                if (ni < 0 || ni == n || nj < 0 || nj == n || check[ni][nj]) continue;
                if (grid[ni][nj]) return level - 1;
                check[ni][nj] = true;
                q.push(make_pair(ni, nj));
            }
            if (--size == 0) {
                size = q.size();
                level++;
            }
        }
        return 0;
    }
};