bfs/dfs-岛屿数量

思路

以每个grid[i][j]为起点搜索（访问过的跳过），套bfs或者dfs的模板，注意边界条件。这个题不用额外维护一个visited的表，可以原地把grid[i][j]置为'0'

bfs:

class Solution {
public:
    /**
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>> 
     * @return int整型
     */
    int dx[4] = {0,0,-1,1};
    int dy[4] = {-1,1,0,0};
    int solve(vector<vector<char> >& grid) {
        // write code here
        int m = grid.size();
        if(!m) return 0;
        int n = grid[0].size();
        int nislands = 0;
        queue< pair<int, int> > q;
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                if(grid[i][j] == '1'){
                    q.push(pair<int, int>(i, j));
                    grid[i][j] = '0';
                    while(!q.empty()) {
                        int y = q.front().first;
                        int x = q.front().second;
                        for(int k = 0; k < 4; k++) {
                            int xx = x+dx[k];
                            int yy = y+dy[k];
                            if(xx <0 || yy < 0 || xx >= n || yy >= m) continue;
                            if(grid[yy][xx] == '1') {
                                q.push(pair<int,int>(yy,xx));
                                grid[yy][xx] = '0';
                            }
                        }
                        q.pop();
                    }
                    nislands++;
                }
            }
        }
        return nislands;
    }
};

dfs:

class Solution {
public:
    /**
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>> 
     * @return int整型
     */
    int dx[4] = {0,0,-1,1};
    int dy[4] = {-1,1,0,0};
    int m_;
    int n_;
    void dfs(int i, int j, vector<vector<char> >& grid) {
        for(int k = 0; k < 4; k++) {
            int yy = i + dy[k];
            int xx = j + dx[k];
            if(yy < 0 || xx < 0 || yy >= m_ || xx >= n_) continue;
            if(grid[yy][xx] == '1') {
                grid[yy][xx] = '0';
                dfs(yy, xx, grid);
            }
        }
    }
    int solve(vector<vector<char> >& grid) {
        // write code here
        int m = grid.size();
        if(!m) return 0;
        int n = grid[0].size();
        m_ = m;
        n_ = n;
        int nislands = 0;
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                if(grid[i][j] == '1') {
                    grid[i][j] = '0';
                    dfs(i, j, grid);
                    nislands++;
                }
            }
        }
        return nislands;
    }
};