岛屿数量习题分析

习题：（leetcode 200）

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

分析:

使用方法为DFS，将遇到的“岛屿”更改为0，表示已探索。以二维数组作为坐标系，设置行列，进行探索。因为岛屿为1，水为0，可以将遍历时遇到的岛屿转化为0，再让其上下左右四个方向进行搜索，遇到1就转变为0。当四个方向的搜索结果都是0时，再进行下一个坐标的遍历。依次将每个点都遍历一遍。

代码分析：

class Solution {
public:int numIslands(vector<vector<char>>& grid) {// 如果网格为空或第一个元素为空，则没有岛屿if (grid.empty() || grid[0].empty()) return 0;int result = 0; // 岛屿数量int row = grid.size(); // 网格的行数int col = grid[0].size(); // 网格的列数// 遍历网格中的每个单元格for (int i = 0; i < row; ++i) {for (int j = 0; j < col; ++j) {// 如果单元格是陆地，则开始深度优先搜索if (grid[i][j] == '1') {++result; // 发现新岛屿，岛屿数量加1dfs(grid, i, j); // 使用深度优先搜索标记所有相连的陆地}}}// 返回岛屿总数return result;}// 辅助函数，执行深度优先搜索void dfs(vector<vector<char>>& grid, int x, int y) {// 检查当前位置是否超出网格边界或是否为水if (x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size() || grid[x][y] == '0') {return;}// 将当前位置标记为已访问（即设置为水）grid[x][y] = '0';// 递归地访问当前位置的上下左右四个方向dfs(grid, x - 1, y); // 上dfs(grid, x + 1, y); // 下dfs(grid, x, y - 1); // 左dfs(grid, x, y + 1); // 右}
};