Problem: 200. 岛屿数量
解析
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
|
class Solution {
private:
void modifyGrid(vector<vector<char>> &grid, int i, int j) {
if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() ||
grid[i][j] != '1') {
return;
}
grid[i][j] = '2';
vector<vector<int>> dir = { {1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (auto e : dir) {
int newI = i + e[0];
int newJ = j + e[1];
modifyGrid(grid, newI, newJ);
}
}
public:
int numIslands(vector<vector<char>> &grid) {
int res = 0;
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[0].size(); ++j) {
if (grid[i][j] == '1') {
++res;
modifyGrid(grid, i, j);
}
}
}
return res;
}
};
|
BFS emplace解析
广度优先遍历，遇到陆地就把这个岛屿陆地都标记为已访问。
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
|
class Solution {
public:
int numIslands(vector<vector<char>> &grid) {
int res = 0;
queue<pair<int, int>> gridQueue;
vector<vector<int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[0].size(); ++j) {
if (grid[i][j] == '1') {
++res;
gridQueue.emplace(i, j);
while (!gridQueue.empty()) {
int nowI = gridQueue.front().first;
int nowJ = gridQueue.front().second;
gridQueue.pop();
for (auto e : dir) {
int newI = nowI + e[0];
int newJ = nowJ + e[1];
if (newI < 0 || newI >= grid.size() || newJ < 0 ||
newJ >= grid[0].size() || grid[newI][newJ] != '1') {
continue;
}
gridQueue.emplace(newI, newJ);
grid[newI][newJ] = '2';
}
}
}
}
}
return res;
}
};
|
不要使用
1
| gridQueue.emplace({newI, newJ});
|
会报错emplace找不到对应的模板，而直接传emplace(newI,newJ)不会报错是因为自动调用了pair的构造函数
可以看到源码里
调用了完美转发的方法，使用了std::forward之后，可以将传入的函数参数按照其原类型进一步传入参数中，从而使右值引用的参数类型可以触发类的移动构造函数。
也可以显式使用构造函数
1
| gridQueue.emplace(make_pair(newI, newJ));
|
