1 solutions

  • 1
    @ 2025-4-25 19:04:53
    #include<bits/stdc++.h>
    using namespace std;
    int dx[]={-1,1,0,0};
    int dy[]={0,0,-1,1};
    typedef pair<int,int> PII;
    #define x first
    #define y second
    const int N=1010,M=1010;
    PII q[N*N];
    int g[N][M];
    bool st[N][M];
    int n,m;
    int bfs(int sx,int sy)
    {
    	int hh=0,tt=-1;
    	q[++tt]={sx,sy};
    	st[sx][sy]=1;
    	while(hh<=tt)
    	{
    		PII t=q[hh++];
    		for(int i=0;i<4;i++)
    		{
    			int a=t.x+dx[i],b=t.y+dy[i];
    			if(a<0||a>n||b<0||b>m) continue;
    			if(g[a][b]==0) continue;
    			if(st[a][b])  continue;
    			q[++tt]={a,b};
    			st[a][b]=1;
    		}
    	}
    	return hh;
    }
    int main()
    {
    	cin>>n>>m;
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=m;j++)
    		{
    			cin>>g[i][j];
    		}
    	}
    	int maxv=0,minv=1e7;
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=m;j++)
    		{
    			if(!st[i][j]&&g[i][j]==1)
    			{
    				int t=bfs(i,j);
    				maxv=max(maxv,t);
    				minv=min(minv,t);
    			}
    		}
    	}
    	cout<<maxv-minv;
    	return 0;
    }
    

    Information

    ID
    671
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    5
    Tags
    # Submissions
    14
    Accepted
    6
    Uploaded By