题目：
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;
}
};
|
