深度優(yōu)先搜索
- 思路：
- 假設(shè)在 (r, c) 格子位置，r 為所處行，c 為所處的列；
- 遇到陸地格子之后，遍歷搜索其上下左右周圍的陸地格子，但是不能超出邊界，即對應(yīng)的數(shù)組下標(biāo)不越界；
- 為了避免重復(fù)多次搜索，搜索到陸地格子之后將其標(biāo)記染色；
- 四周搜索完所有的陸地格子，即為一個(gè)島嶼；
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int nr = grid.size();
if (nr == 0) {
return 0;
}
int nc = grid[0].size();
int num = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
++num;
dfs(grid, r, c);
}
}
}
return num;
}
private:
void dfs(std::vector<std::vector<char>>& grid, int r, int c) {
int nr = grid.size();
int nc = grid[0].size();
// mark
grid[r][c] = '0';
// up
if (r - 1 >= 0 && grid[r - 1][c] == '1') {
dfs(grid, r - 1, c);
}
// down
if (r + 1 < nr && grid[r + 1][c] == '1') {
dfs(grid, r + 1, c);
}
// left
if (c - 1 >= 0 && grid[r][c - 1] == '1') {
dfs(grid, r, c - 1);
}
// right
if (c + 1 < nc && grid[r][c + 1] == '1') {
dfs(grid, r, c + 1);
}
}
};- 查看了力扣上的思路，有一個(gè)總結(jié)格子DFS算法的帖子尤為經(jīng)典，可以后續(xù)總結(jié)的時(shí)候參考
- 島嶼類問題 DFS 算法框架
文章來源地址http://www.zghlxwxcb.cn/news/detail-762882.html
文章來源：http://www.zghlxwxcb.cn/news/detail-762882.html
到了這里，關(guān)于力扣200. 島嶼數(shù)量的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
