样例过了 WA
查看原帖
样例过了 WA
752802
fuguizait楼主2023/12/25 23:27
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int,int>PII;
const int N = 260;
int a[N][N]; //整个海面
bool s[N][N]; //该点是否已经搜索
int a_num[62510]; //连通块面积i对应的个数
int n,m;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

//返回元素1(石油)
inline int bfs(int z, int b)
{
    int num = 0;
    queue<PII>q; 
    q.push({z,b}); //该点入队
    s[z][b] = true;
    num ++; //石油加一
    
    while(!q.empty()) //当队列不空
    {
        auto t = q.front();
        q.pop();
        
        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 && a[x][y] == 1 && s[x][y] == false)
            {
                //如果在边界内 且还尚未搜索 且下一步要搜到的点是石油
                q.push({x,y});
                s[x][y] = true; //更新该点搜索状态
                num ++;
            }
        }
    }
    a_num[num] ++; //该数目的连通块数目加一
    return num;
 }

int main()
{
    int ans = 0; //数量
    int nums = 0;
    cin.tie(0);
    while(cin >> n >> m && n && m)
    {
        memset(a,0,sizeof(a));
		memset(a_num,0,sizeof(a_num));
        for (int i = 1;i <= n; i ++)
    {
        for (int j = 1; j <= m; j ++)
        {
            cin >> a[i][j]; 
        }
    }
    
    for (int i = 1;i <= n; i ++)
    {
        for (int j = 1; j <= m; j ++)
        {
            if (!s[i][j] && a[i][j] == 1)
            {
                nums = max(nums, bfs(i,j));
                ans ++;
            }
        }
    }
    }
    
    cout << ans << endl;
    for (int i = 1; i <= nums; i ++)
    {
        if (a_num[i] > 0)
        {
            cout << i <<' ' << a_num[i] << endl;
        }
    }
    return 0;
}


2023/12/25 23:27
加载中...