岛屿数量

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
class Solution {
public:
    //DFS---深度优先遍历
    int numIslands(vector<vector<char>>& grid) 
    {
        int count = 0;
        for (int i = 0; i < grid.size(); i++)
        {
            for (int j = 0; j < grid[0].size(); j++)
            {
                //如果找到一个顶点为1，就利用dfs把其四周所有顶点找出来，并且设置为访问过的标记
                if (grid[i][j] == '1')
                {
                    dfs(grid,i,j);
                    count++;
                }
            }
        }
        return count;
    }
    void dfs(vector<vector<char>>& grid,int r,int c)
    {
        if (r < 0 || c < 0 || r >= grid.size() || c >= grid[0].size()||grid[r][c]=='0') return;
        grid[r][c] = '0';
        dfs(grid, r + 1, c);
        dfs(grid, r, c + 1);
        dfs(grid, r - 1, c);
        dfs(grid, r, c - 1);
    }
};

void test()
{
    vector<vector<char>> grid ={
        {'1','1', '0', '0', '0'} ,
         {'1','1', '0', '0', '0'} ,
          {'0','0', '1', '0', '0'} ,
           {'0','0', '0', '1', '1'} ,
    };
    Solution s;
    int ret=s.numIslands(grid);
    cout << "岛屿数量有：" << ret << "个" << endl;
}
int main()
{
    test();
    return 0;
}

    class Solution {
        vector<vector<int>> dir = { {-1,0},{1,0},{0,1},{0,-1} };//记录方向的数组
    public:
        //BFS---广度优先遍历
        int numIslands(vector<vector<char>>& grid)
        {
            if (grid.empty())
                return 0;
            int count = 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);
                        count++;
                    }
                }
            }
            return count;
        }
        // 扩张陆地函数（扩张至极限，直到周围都是水，不存在可连接的陆地。目的是把可连接的陆地置为水）
        void bfs(vector<vector<char>>& grid, int r, int c)
        {
            //将当前的陆地放入队列中，然后设置为已经访问的标志
            queue<pair<int, int>> q;
            q.push({ r,c });
            grid[r][c] = '0';
            //当队列为空，此次扩张完成
            while (!q.empty())
            {
                //队头元素出队
                pair<int,int> temp=q.front();
                q.pop();
                //四个方向同时扩张，直到遇到大海
                //如果越界了，或者是水域，那么就跳过下面代码执行，继续将队列中剩余元素拿出来，进行扩张
                int R = temp.first;//获取行
                int C = temp.second;//获取列
                for (int i = 0; i < 4; i++)
                {
                        int rr = R + dir[i][0];
                        int cc = C + dir[i][1];
                        if (rr < 0 || cc < 0 || rr >= grid.size() || cc >= grid[0].size() || grid[rr][cc] == '0')
                            continue;
                        //把新找到的陆地加入队列
                        q.push({ rr,cc });
                        //入队就表示这块陆地已经合并至本岛屿，已经被使用过
                        grid[rr][cc] = '0';
                 }
            }

        }
    };