【c++刷题】leetcode 200. 岛屿数量

思路

深度优先搜索是一种递归的搜索算法，其核心思想是从一个节点开始，沿着一条路径尽可能深地探索下去，直到无法继续，然后回溯到上一个节点，继续探索其他路径。在本题中，我们可以将二维网格中的每一个 ‘1’（陆地）看作一个节点，通过 DFS 算法将与该节点相连的所有陆地都标记为已访问，这样就可以将一个岛屿整体处理。通过遍历整个二维网格，每当遇到一个未被访问的陆地时，就进行一次 DFS 搜索，每进行一次 DFS 搜索就意味着发现了一个新的岛屿，最终统计 DFS 搜索的次数即可得到岛屿的数量。

解答

class Solution {
public:
    int rows;
    int cols;

    void dfs(vector<vector<char>>& grid, int i, int j)
    {
       // cout << "i="<<i<<", rows="<<this->rows<<", j="<<j<<", cols="<<this->cols<<endl;
        if (i<0 || i>=this->rows || j<0 || j>=this->cols) return;
        if (grid[i][j] == '0') return;

        grid[i][j] = '0';

        dfs(grid,i+1,j);
        dfs(grid,i-1,j);
        dfs(grid,i,j-1);
        dfs(grid,i, j+1);
    }

    int numIslands(vector<vector<char>>& grid) {
        int ans = 0;

        this->rows = grid.size();
        this->cols = grid[0].size();

        for (int i=0; i<rows; ++i)
        {
            for (int j=0; j<cols; ++j)
            {
                if (grid[i][j] == '1')
                {
                    dfs(grid, i, j);
                    ans +=1;
                }                
            }
        }
        return ans;
    }
};