给定一个由'1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
输入:
11110
11010
11000
00000
输出:1
示例 2:
输入:
11000
11000
00100
00011
输出: 3
代码:
#include <iostream>
#include <queue>
using namespace std;
//BFS 广度优先遍历
class Solution{
private:
queue<int> island;
int count;
int x;
int y;
int xx;
int yy;
public:
int numIslands(vector<vector<char> > &grid){
int rows = grid.size();
int cols = rows>0?grid[0].size():0;
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
if(rows == 0 || cols == 0){
return 0;
}
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
if(grid[i][j] == '1'){
island.push(i);
island.push(j);
grid[i][j] == '0';
while(!island.empty()){
x= island.front();
island.pop();
y = island.front();
island.pop();
for(int k=0;k<4;k++){
xx = x+dx[k];
yy = y+dy[k];
if(xx<0||xx>=rows||yy<0||yy>=cols){
continue;
}
if(grid[xx][yy] == '1'){
grid[xx][yy] = '0';
island.push(xx);
island.push(yy);
}
}
}
//队列为空说明为岛屿
count++;
}
}
}
return count;
}
};