Leetcode 200. 岛屿数量（C++）（小白学习之路）

旧城等待， 2023-07-18 11:22 10阅读 0赞

题目描述：

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

示例 1:

输入:  
11110  
11010  
11000  
00000

输出: 1  
示例 2:

输入:  
11000  
11000  
00100  
00011

输出: 3

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/number-of-islands  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这周终于做到了图相关的算法题，这道题目应该属于图算法中比较基础的，通过DFS或者BFS把‘1’附近所有的‘1’遍历完毕就算一个岛，从左上到右下完整遍历一遍即可判断岛屿数量，这里回忆了一下DFS使用到的数据结构是栈，BFS使用的是队列，两者都可以直接使用C++STL里的标准容器实现，而不用自己再去写一个容器。

这里我用的是BFS，代码如下：

class Solution {
    public:
        bool inIsland(vector<vector<char>> & grid, pair<int,int>index)  //判断某一点是否越界
        {
            int M = grid.size();
            if(!M) return false;
            int N = grid[0].size();
            if(index.first>=0&&index.first<M&&index.second>=0&&index.second<N) return true;
            else return false;
        }
        int numIslands(vector<vector<char>>& grid) {
            int M = grid.size();
            if(!M) return 0;
            int N = grid[0].size();    //行数M，列数N
            int res=0;
            queue<pair<int,int>> BFS;     //BFS使用队列初始化
            for(int i=0;i<M;i++)
            {
                for(int j=0;j<N;j++)            //从（0,0）开始遍历
                {
                    if(grid[i][j]=='0') continue;    //‘0’说明是海水，直接跳过，少了这句continue有的案例会超时
                    if(grid[i][j]=='1')
                    {
                        BFS.push(make_pair(i,j));    //遍历到‘1’，入队
                        //grid[i][j] = 0;
                        res++;                        //岛屿数量+1
                        while(!BFS.empty())            //遍历这个‘1’附近的所有‘1’作为一个岛屿
                        {
                            pair<int,int> temp = BFS.front();
                            BFS.pop();
                            if(grid[temp.first][temp.second]=='0') continue;    //这句其实应该可以省略
                            grid[temp.first][temp.second] = '0';    //已遍历过的置‘0’表示已遍历
                            pair<int,int> up = make_pair(temp.first-1, temp.second);
                            pair<int,int> down = make_pair(temp.first+1, temp.second);
                            pair<int,int> left = make_pair(temp.first, temp.second-1);
                            pair<int,int> right = make_pair(temp.first, temp.second+1);
                            if(inIsland(grid,up)&&grid[up.first][up.second]=='1') BFS.push(up);
                            if(inIsland(grid,down)&&grid[down.first][down.second]=='1') BFS.push(down);
                            if(inIsland(grid,left)&&grid[left.first][left.second]=='1') BFS.push(left);
                            if(inIsland(grid,right)&&grid[right.first][right.second]=='1') BFS.push(right);            //当前访问的点，上、下、左、右若为‘1’则入队，进入广度优先遍历，直到所有的‘1’遍历完，这一个岛屿宣告遍历结束
                        }
                    }
    
                }
            }
            return res;
    
        }
    };

优化点：1. 上、下、左、右四个点的操作可以通过两个数组\[-1,1,0,0\], \[0,0,-1,1\]来实现

2.并查集的方法

并查集的方法目前还没有完全掌握，等到二刷时尝试一下，也会尝试写一下DFS，通过做题来复习算法。