淘先锋技术网

首页 1 2 3 4 5 6 7

给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。
在这里插入图片描述

提示:
m == grid.length
n== grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 ‘0’ 或 ‘1’
在这里插入图片描述

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        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'){
                bfs(grid,i,j);
                cnt++;
            }
        }
        return cnt;
    }
    void bfs(vector<vector<char>>& grid,int i,int j){
        if( i<0 || i>=grid.size() || j<0 || j>=grid[0].size() || grid[i][j]=='0' )
            return;
        grid[i][j]='0';
        bfs(grid,i-1,j);//left
        bfs(grid,i+1,j);//right
        bfs(grid,i,j-1);//up
        bfs(grid,i,j+1);//down
    }
};