题解 | #岛屿数量#

// 栈实现深度优先遍历 dfs
class Solution {
public:
    int solve(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int count =0;
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                if(grid[i][j]!='0') {
                    dfs(grid, i, j);
                    count ++;
                }
            }
        }
        return count;
    }

    void dfs(vector<vector<char>>& grid, int x, int y) {
        int m = grid.size(), n= grid[0].size();
        if(x<0 || x>=m || y<0 || y>=n || grid[x][y]=='0')
            return ;

        grid[x][y] = '0';
        int dx[4] = {0,0,-1,1};
        int dy[4] = {1,-1,0,0};
        for(int i=0; i<4; i++) {
           dfs(grid, x+dx[i], y+dy[i]);
        }

        return ;
    }
};

// 队列实现广度优先遍历 bfs
class Solution {
public:
    int solve(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int count =0;
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                if(grid[i][j]=='1') {
                    bfs(grid, i, j);
                    count ++;
                }
            }
        }
        return count;
    }

    void bfs(vector<vector<char>>& grid, int x, int y) {
        int m = grid.size(), n = grid[0].size();
        queue<vector<int>> que;
        que.push({x, y});
        while(!que.empty()) {
            vector<int> v = que.front(); que.pop();
            x = v[0]; y = v[1];
            if(x>=0 && x<m && y>=0 && y<n && grid[x][y]!='0') {
                grid[x][y] = '0';
                int dx[4] = {0,0,-1,1};
                int dy[4] = {1,-1,0,0};
                for(int i=0; i<4; i++) {
                    que.push({x+dx[i], y+dy[i]});
                }
            }            
        }
        return ;
    }
};