bfs求连通块数量

老裸题了，也可以看成flood fill

时间复杂度$O(N^2$)，空间复杂度$O(N^2$)

AC代码

class Solution {
public:
    typedef pair<int,int> PAIR;
    int n , m;
    vector<vector<bool>> st;
    int dx[4] = {0 ,0 ,-1, 1}, dy[4] = {1, -1, 0, 0};

    void bfs(int x, int y, vector<vector<char>>& g){
        queue<PAIR> q;
        q.push({x, y});
        st[x][y] = true;

        while (q.size()){
            auto t = q.front();
            q.pop();
            for (int i = 0 ; i < 4 ; i ++){
                int a = t.first + dx[i], b = t.second + dy[i];
                if (a < 0 || a >= n || b < 0 || b >= m || g[a][b] == '0' || st[a][b]) continue;
                st[a][b] = true;
                q.push({a, b});
            }
        }
    }

    int numIslands(vector<vector<char>>& g) {
        n = g.size(), m = g[0].size();
        st = vector<vector<bool>> (n , vector<bool> (m + 1, false));
        int res = 0;
        for (int i = 0 ; i < n ; i ++){
            for (int j = 0 ; j < m ; j ++){
                if (g[i][j] == '1' && st[i][j] == false){
                    res ++;
                    bfs(i , j, g);
                }
            }
        }
        return res;
    }
};