题解 | #岛屿数量#
岛屿数量
http://www.nowcoder.com/practice/0c9664d1554e466aa107d899418e814e
这个题是典型的dfs的题，需要注意的是不要重复查找。所以需要对查找过的岛屿进行标记。
class Solution {
public:
/**
* 判断岛屿数量
* @param grid char字符型vector<vector<>>
* @return int整型
*/
int solve(vector<vector<char> >& grid) {
int count = 0;
// write code here
vector<vector<int>> search(grid.size(),vector<int> (grid[0].size(),false));
for(int i=0;i<grid.size();i++){
for(int j=0;j<grid[0].size();j++){
if(search[i][j]==1 || grid[i][j] == '0'){
search[i][j] = 1;
continue;
}
dfs(grid, search, i, j);
count++;
}
}
return count;
}
void dfs(vector<vector<char> >& grid,vector<vector<int> >& search,int i,int j){
if(search[i][j] == 1){
return;
}
search[i][j] = 1;
if(j-1 >= 0 && grid[i][j-1] == '1'){
dfs(grid, search, i, j-1);
}
if(i-1 >= 0 && grid[i-1][j] == '1'){
dfs(grid, search, i-1, j);
}
if(i+1 < grid.size() && grid[i+1][j] =='1'){
dfs(grid, search, i+1, j);
}
if(j+1 < grid[0].size() && grid[i][j+1] == '1'){
dfs(grid, search, i, j+1);
}
}
};
