题目描述

这是一道非常简单的BFS。
思路：
遍历每一个坐标，如果有第一次遍历到的陆地，那么使用队列BFS找他附近的陆地，并再次对新陆地使用BFS找到新陆地附近的陆地，最后会得到，每个小岛所有陆地的坐标。
代码详解
1.

int dx[4] = {0,0,-1,1};//定义四个方向，作用详见后文
int dy[4] = {1,-1,0,0};

2.

vector<vector<char>> g(n+1,vector<char>(m+1));//嵌套vector定义了一个二维字符串
//用于存储图像，n+1行m+1列，字符串默认初始为'\0'
vector<vector<bool>> st(n+1,vector<bool>(m+1,false));//定义二维bool类型用于
//存储每个坐标是否被遍历，false表示初始为false;

3.

vector<pair<int,int>> res;//存储面积和周长
//例如res = {
//    {3, 6}, // 第一个连通区域的大小为 3，周长为 6
//    {1, 4}  // 第二个连通区域的大小为 1，周长为 4
//};
vector<vector<pair<int,int>>> num;//存储坐标集合，其大小表示岛屿个数
//例如：num = {
//           {{1, 1}, {1, 2}, {2, 2}}, // 第一个连通区域
//            {{3, 3}}                   // 第二个连通区域
//       };//表示两个岛屿，以及每个岛屿的陆地的坐标

    vector<pair<int,int>> tmp;//存储坐标
    queue<pair<int,int>> q;//队列

样例

#include<iostream> 
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};

int main(){
    int n,m;
    cin>>n>>m;

    vector<vector<char>> g(n+1,vector<char>(m+1));
    vector<vector<bool>> st(n+1,vector<bool>(m+1,false));//1

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>g[i][j];

    vector<pair<int,int>> res;
    vector<vector<pair<int,int>>> num;//2

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)//遍历每一个坐标
            {
                if (st[i][j]||g[i][j]=='0') continue;//坐标已遍历或坐标为0（不是陆地）则跳过
                else{//否则进行bfs

                    vector<pair<int,int>> tmp;//3
                    queue<pair<int,int>> q;

                    q.push({i,j});//坐标入队
                    while(q.size() )
                    {
                        auto t=q.front() ;
                        q.pop() ;//出队运算
                        if(st[t.first][t.second]) continue;//已遍历则跳过
                        else st[t.first][t.second] = true;//否则进行标注
                        tmp.push_back({t.first,t.second});//将其坐标输入tmp数组
                        for(int i=0;i<4;i++)//遍历四个方向
                        {
                            int x=t.first+dx[i];
                            int y=t.second+dy[i];
                            if(x>=1&&x<=n&&y>=1&&y<=m&&g[x][y]=='1'&&st[x][y]==false)
                                q.push({x,y}); //符合条件则入队
                         } 
                    }
                    num.push_back(tmp);//最后得出这一岛屿的所有坐标后，把坐标集合输入num
                }

            }
    for(vector<pair<int,int>> t:num)//遍历每一个岛屿
        {
            int l=0;
            int s=t.size();
            for(auto tt:t)//遍历每一个岛屿中的坐标，求周长
                {
                    for(int i=0;i<4;i++)
                        {
                            int x=tt.first+dx[i];
                            int y=tt.second+dy[i];
                            if(x<1||x>n||y<1||y>m||g[x][y]=='0')//如果改坐标挨着边界则为周长 {
                                l++;
                                break;
                            }
                        }
                }
            res.push_back({s,l}); //把面积和周长输入res
        }
    sort(res.begin() ,res.end() );
    for(auto k : res) cout<<k.first<<' '<<k.second<<endl;
    return 0;
}