C++刷题之旅（53）

LeetCode算法入门（第五十三天） 深度优先搜索 200.岛屿数量

class Solution {
public:

    void DFS(vector<vector<char>>& grid, int x, int y){
        int row = grid.size();
        int col = grid[0].size();

        grid[x][y] = '0';   //遍历过的点标记为0
        
        //上，下，左，右四个方向搜索
        if(x-1 >= 0 && grid[x-1][y] == '1'){
            DFS(grid, x-1, y);
        }
        if(x+1 < row && grid[x+1][y] == '1'){
            DFS(grid, x+1, y);
        }
        if(y-1 >= 0 && grid[x][y-1] == '1'){
            DFS(grid, x, y-1);
        }
        if(y+1 < col && grid[x][y+1] == '1'){
            DFS(grid, x, y+1);
        }
    }

    int numIslands(vector<vector<char>>& grid) {
        int row = grid.size();
        if(row == 0){
            return 0;
        }
        int col = grid[0].size();
        int land = 0;
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(grid[i][j] == '1'){
                    land++;
                    DFS(grid, i, j);
                }
            }
        }

        return land;
    }
};

547.省份数量

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int m = isConnected.size();
        vector<vector<bool>> visited(m, vector<bool>(m, false));
        int res = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = i; j < m; ++j) {
                if (isConnected[i][j] == 1 && !visited[i][j]) {
                    dfs(isConnected, visited, i, j);
                    ++res;
                }
            }
        }
        return res;
    }
private:
    void dfs(vector<vector<int>>& isConnected, vector<vector<bool>>& visited, int i, int j) {
        visited[i][j] = true;
        for (int k = 0; k < isConnected.size(); ++k) {
            if (isConnected[j][k] == 1 && !visited[j][k]) {
                dfs(isConnected, visited, j, k);
            }
        }
    }
};