时间轴

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
#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 = 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;
	}
};

leetcoe hot 100 rewrite, 发现之前的写法会导致 同一个节点可能被多次入栈 ， 因此 visited 标记表示为已经入栈过更好。

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 <stack>
#include <utility>

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

class Solution {
    public:
        int numIslands(vector<vector<char> > &grid)
        {
                // 1 <= m, n <= 300
                int i, j, m = grid.size(), n = grid[0].size();
                vector<vector<bool> > visited(m, vector<bool>(n, false));
                stack<pair<int, int> > stk;
                int nr_island = 0;

                for (i = 0; i < m; i++) {
                        for (j = 0; j < n; j++) {
                                if (visited[i][j] || grid[i][j] == '0')
                                        continue;
                                // DFS
                                stk.push({ i, j });
                                visited[i][j] = true; // 表示已经入栈

                                while (!stk.empty()) {
                                        auto [ipos, jpos] = stk.top();
                                        stk.pop();

                                        // 上
                                        if (ipos - 1 >= 0 && !visited[ipos - 1][jpos] &&
                                            grid[ipos - 1][jpos] == '1') {
                                                stk.push({ ipos - 1, jpos });
                                                visited[ipos - 1][jpos] = true;
                                        }

                                        // 下
                                        if (ipos + 1 < m && !visited[ipos + 1][jpos] &&
                                            grid[ipos + 1][jpos] == '1') {
                                                stk.push({ ipos + 1, jpos });
                                                visited[ipos + 1][jpos] = true;
                                        }

                                        // 左
                                        if (jpos - 1 >= 0 && !visited[ipos][jpos - 1] &&
                                            grid[ipos][jpos - 1] == '1') {
                                                stk.push({ ipos, jpos - 1 });
                                                visited[ipos][jpos - 1] = true;
                                        }

                                        // 右
                                        if (jpos + 1 < n && !visited[ipos][jpos + 1] &&
                                            grid[ipos][jpos + 1] == '1') {
                                                stk.push({ ipos, jpos + 1 });
                                                visited[ipos][jpos + 1] = true;
                                        }
                                }

                                nr_island++;
                        }
                }

                return nr_island;
        }
};