题目描述
给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。
出处
思路
经典扫描就行。
代码
class Solution {
public:
void del(int i, int j, int m, int n, vector<vector<char>>& grid){
if(i<0||i>=m||j<0||j>=n) return;
if(!(grid[i][j]-'0')) return;
grid[i][j]='0';
del(i-1,j,m,n,grid);
del(i,j-1,m,n,grid);
del(i+1,j,m,n,grid);
del(i,j+1,m,n,grid);
}
int numIslands(vector<vector<char>>& grid) {
int m=grid.size();
int n=grid[0].size();
int ans=0;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++){
if(grid[i][j]-'0'){
ans++;
del(i,j,m,n,grid);
}
}
return ans;
}
};