岛屿数量

最新推荐文章于 2024-02-22 10:00:00 发布

rdc01234

最新推荐文章于 2024-02-22 10:00:00 发布

阅读量189

点赞数

分类专栏： leetcode C++

本文链接：https://blog.csdn.net/Random_R/article/details/103484998

版权

leetcode C++ 专栏收录该内容

116 篇文章

订阅专栏

岛屿数量

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

示例 2:

分析：

进行深度遍历或广度遍历，每进行一次遍历确定当前坐标所在地是不是一个岛屿。

纯广度遍历(代码比较复杂)

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if(grid.size() < 1) return 0;
//         岛屿数量
        int count = 0;
//         遍历每一个节点
        for(int i=0; i<grid.size(); i++){
            for(int j=0; j<grid[0].size(); j++){
//                 进行广度遍历
                if(BFS(grid,i,j)) count ++;
            }
        }
        return count;
    }
    /*
    111
    010
    111
    */
//     进行广度遍历，有节点就return
    bool BFS(vector<vector<char>>& grid, int x, int y){
        if(grid[x][y] != '1') return false;
//         广度遍历
        queue<int> q;   // 偶数表示行，奇数表示列
//         保存当前节点
        q.push(x);
        q.push(y);
//         遍历岛屿的每个东东
        while(!q.empty()){
//             拿到待遍历的坐标
            x = q.front();
            q.pop();
            y = q.front();
            q.pop();
//             遍历grid[i][j]的右边坐标
            for(int j=y+1; j<grid[x].size(); j++){
                if(grid[x][j] == '1'){
                    q.push(x);
                    q.push(j);
                }else
                    break;
            }
//             遍历grid[i][j]的左边坐标
            for(int j=y-1; j>= 0; j--){
                if(grid[x][j] == '1'){
                    q.push(x);
                    q.push(j);
                }else
                    break;
            }
//             加入grid[i][j]上面的坐标
            int up_x = (x-1)<=0?0:(x-1);
            if(grid[up_x][y] == '1'){
                q.push(up_x);
                q.push(y);
            }
//             加入grid[i][j]下面的坐标
            int down_x = (x+1)>=grid.size()?x:(x+1);
            if(grid[down_x][y] == '1'){
                q.push(down_x);
                q.push(y);
            }
//             将当前坐标改为已经遍历
            grid[x][y] = '2';
        }
        return true;
    }
};

深度遍历

自己参考广度遍历写吧，只需要将BFS函数中的左右查找改为上下查找，将上下节点入队列改为将左右节点入队列即可

深度遍历+递归(代码简单易读)

class Solution {
private:
        char replace = '2';
        char land = '1';
        void DFS(vector<vector<char>>& grid, int row, int col);
public:
    int numIslands(vector<vector<char>>& grid) {
//             深度遍历
            int count = 0;      // 岛屿数量
            for(int i=0; i<grid.size(); i++){
                    for(int j=0; j<grid[i].size(); j++){
                            if(grid[i][j] == land){
//                                     没有遍历过就从这一点开始遍历
                                    DFS(grid, i, j);
                                    count ++;
                            }
                    }
            }
            return count;
    }
};

void Solution::DFS(vector<vector<char>>& grid, int row, int col){
//         合理性判断
        if(row < 0 || col < 0) return;
        if(row >= grid.size() || col >= grid[row].size()) return;
//         递归结束条件
        if(grid[row][col] != land) return;
//         遍历这一点
        grid[row][col] = replace;
//         递归其他点
        DFS(grid, row-1, col);  // 上
        DFS(grid, row+1, col);          // 下
        DFS(grid, row, col-1);        // 左
        DFS(grid, row, col+1);        // 右
}