时间轴

2025-11-03

init

题目：

P200 岛屿数量

https://leetcode.cn/problems/number-of-islands/description/?envType=study-plan-v2&envId=top-interview-150

DFS判断岛屿数量，本质上是用DFS看连通图的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <vector>
#include <utility>
#include <stack>

using std::vector;
using std::pair;
using std::stack;

class Solution {
    public:
	int numIslands(vector<vector<char> > &grid)
	{
		int m, n;
		m = grid.size();
		n = grid[0].size();
		vector<vector<bool> > visited =
			vector<vector<bool> >(m, vector<bool>(n, false));
		int island_num = 0;
		int i, j;
		stack<pair<int, int> > st;
		for (i = 0; i < m; i++) {
			for (j = 0; j < n; j++) {
				if (visited[i][j] || grid[i][j] =='0') {
					continue;
				}
				st.push({ i, j });
				while (!st.empty()) {
					auto [curr_i, curr_j] = st.top();
					visited[curr_i][curr_j] = true;
					st.pop();
					// 上
					if (curr_i - 1 >= 0 &&
					    !visited[curr_i - 1][curr_j] &&
					    grid[curr_i - 1][curr_j] == '1') {
						st.push({ curr_i - 1, curr_j });
					}

					// 下
					if (curr_i + 1 < m &&
					    !visited[curr_i + 1][curr_j] &&
					    grid[curr_i + 1][curr_j] == '1') {
						st.push({ curr_i + 1, curr_j });
					}

					// 左
					if (curr_j - 1 >= 0 &&
					    !visited[curr_i][curr_j - 1] &&
					    grid[curr_i][curr_j - 1] == '1') {
						st.push({ curr_i, curr_j - 1 });
					}

					// 右
					if (curr_j + 1 < n &&
					    !visited[curr_i][curr_j + 1] &&
					    grid[curr_i][curr_j + 1] == '1') {
						st.push({ curr_i, curr_j + 1 });
					}

				}
				island_num ++;
			}
		}

		return island_num;
	}
};