深度优先搜索 - 岛屿问题
题目描述
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外，你可以假设该网格的四条边均被水包围。
200. 岛屿数量 - 力扣（LeetCode）
示例 ：
输入：grid =
[["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]]。
输出：3
解题思路
1. 问题理解
首先，我们需要明确什么是岛屿。在这个问题中，岛屿是由四面相连的'1'（陆地）形成的区域，并且这些区域完全被'0'（水）包围。我们的目标是计算给定网格中岛屿的数量。
2. 遍历网格
由于我们不知道岛屿的具体位置，因此我们需要遍历整个网格。对于网格中的每个格子，我们检查它是否是陆地（'1'）。
3. 深度优先搜索（DFS）
当我们遇到一个陆地格子时，我们知道我们找到了一座岛屿的一部分。为了计算完整的岛屿数量，我们需要确保我们不会重复计算同一座岛屿的不同部分。这就是DFS派上用场的地方。
DFS是一种递归算法，它从当前格子开始，并尽可能深地搜索所有相邻的陆地格子。在搜索过程中，它将访问过的格子标记为已访问（例如，将其值从'1'更改为'0'），以确保我们不会再次访问它们。
4. 递归搜索
对于当前陆地格子，我们执行以下操作：
- 将当前格子标记为已访问。
- 对当前格子的上、下、左、右四个相邻格子进行递归调用DFS。但是，在调用之前，我们需要检查相邻格子是否在网格范围内内，并且它们是否是陆地（'1'）。
5. 计数岛屿
每次我们从一个未访问的陆地格子开始DFS搜索时，我们都知道我们找到了一座新的岛屿。因此，我们可以在每次开始DFS搜索时增加岛屿计数器。
6. 终止条件
DFS搜索将在以下情况下终止：
- 我们已经访问了网格中的所有格子，并且没有更多的陆地格子可以访问。
- 我们尝试访问一个不在网格范围内的格子。
- 我们尝试访问一个已经访问过的格子（即其值为'0'）。
7. 重复步骤
我们重复上述步骤，直到网格中的所有格子都被访问过。
8. 输出结果
最后，我们输出岛屿计数器的值，即网格中岛屿的数量。
class Solution {
public:int n, m;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int numIslands(vector<vector<char>>& grid) {n = grid.size();m = grid[0].size();int ret = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == '1') {dfs(grid, i, j);ret++;}}}return ret;}void dfs(vector<vector<char>>& grid, int i, int j) {grid[i][j] = '2';for (int k = 0; k < 4; k++) {int tmpx = i + dx[k];int tmpy = j + dy[k];if (tmpx >= 0 && tmpx < n && tmpy >= 0 && tmpy < m &&grid[tmpx][tmpy] == '1') {dfs(grid, tmpx, tmpy);}}}
};