leetcode:99. 岛屿数量
题目
题目描述：
给定一个由 1（陆地）和 0（水）组成的矩阵，你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。
输入描述：
第一行包含两个整数 N, M，表示矩阵的行数和列数。
后续 N 行，每行包含 M 个数字，数字为 1 或者 0。
输出描述：
输出一个整数，表示岛屿的数量。如果不存在岛屿，则输出 0。
思路
遇到一个没有遍历过的节点陆地，计数器就加一，然后把该节点陆地所能遍历到的陆地都标记上（这一步就是为了防止重复计算!）。
在遇到标记过的陆地节点和海洋节点的时候直接跳过.
计数器就是最终岛屿的数量。
下面代码详细注释：
#include <bits/stdc++.h>
using namespace std;
// 定义4个方向
int dir[4][2] = {1, 0, 0, -1, -1, 0, 0, 1};
void dfs(vector<vector<int>> &grid, vector<vector<bool>> &visited, int x, int y)
{
// 终止条件：如果遇到海水或者已经遍历过的岛屿就停下来
if (grid[x][y] == 0 || visited[x][y])
{
return;
}
// 处理当前节点：当前到了(x,y)这个点，首先就把它标记上
visited[x][y] = true;
// 当前节点往下延伸，看它四周的点
for (int i = 0; i < 4; i++)
{
int nextx = x + dir[i][0];
int nexty = y + dir[i][1];
// 基本限制条件：下一个点肯定不能跑到整个大矩阵的外面去
if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size())
continue;
// 递归：这里递归不需要任何条件，因为一进入dfs就会有终止条件来判断
dfs(grid, visited, nextx, nexty);
}
}
int main()
{
int n, m;
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m, 0));
vector<vector<bool>> visited(n, vector<bool>(m, false));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> grid[i][j];
}
}
// count最终岛屿计数
int count = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
// 一个一个陆地开始找，不要觉得麻烦，因为有的陆地已经被标记了，就会直接跳过
if (grid[i][j] == 1 && !visited[i][j])
{
count++;
dfs(grid, visited, i, j);
}
}
}
cout << count << endl;
return 0;
}一定要清楚dfs在这里的作用：
对（x,y）周围的岛屿进行标记！
总结
我这里写的是dfs的第二个模板，第一个模版因为没有终止条件，所以写起来感觉很奇怪，我就没有放，感兴趣去看随想录。