【力扣】100.岛屿数量
AC截图
题目
思路
可以用一个和grid数组大小相同的visit数组记录陆地是否被访问过。
遍历grid数组，对于每一个没有被访问过的陆地，调用依次dfs，再将cnt++即可。
代码
class Solution {
public:
void dfs(vector<vector<char>>& grid,vector<vector<bool>>& visit,int i,int j){
//处理边界
if(i<0 || j<0 || i>=grid.size() || j>=grid[0].size() || grid[i][j]=='0' || visit[i][j]){
return ;
}
visit[i][j]=true;
dfs(grid,visit,i+1,j);
dfs(grid,visit,i,j+1);
dfs(grid,visit,i-1,j);
dfs(grid,visit,i,j-1);
}
int numIslands(vector<vector<char>>& grid) {
vector<vector<bool>> visit(grid.size(),vector<bool>(grid[0].size(),false));
int cnt = 0;
for(int i=0;i<grid.size();i++){
for(int j=0;j<grid[0].size();j++){
if(grid[i][j]=='1' && !visit[i][j]){
dfs(grid,visit,i,j);
cnt++;
}
}
}
return cnt;
}
};