1 solutions

  • 0
    @ 2026-4-13 16:19:50
    #include<bits/stdc++.h>
    using namespace std;
    const int N=1010;
    char g[2*N][2*N]; //因为有正负,所以开了两倍的空间
    bool st[2*N][2*N];
    int dx[]={-1,-1,0,0,1,1};
    int dy[]={-1,0,-1,1,0,1};
    typedef pair<int,int> PII;
    #define x first
    #define y second
    void bfs(int x,int y)
    {
    	queue<PII> q;
    	q.push({x,y});
    	while(q.size())
    	{
    		auto t=q.front();
    		q.pop();
    		for(int i=0;i<6;i++)
    		{
    			int a=t.x+dx[i],b=t.y+dy[i];
    			if(a<0||a>=2*N||b<0||b>=2*N) continue;
    			if(g[a][b]==0) continue;
    			if(st[a][b]) continue;
    			st[a][b]=1;
    			q.push({a,b});
    		}
    	}
    }
    int main()
    {
    	int n;
    	cin>>n;
    	for(int i=1;i<=n;i++)
    	{
    		int x,y;
    		cin>>x>>y;
    		g[x+1000][y+1000]=1; //累加偏移量
    	}
    	int cnt=0;
    	for(int i=0;i<2*N;i++)
    	{
    		for(int j=0;j<2*N;j++)
    		{
    			if(!st[i][j]&&g[i][j]==1)
    			{
    				st[i][j]=1;
    				cnt++;
    				bfs(i,j);
    			}
    		}
    	}
    	cout<<cnt;
    	return 0;
    }
    
    • 1

    Information

    ID
    2759
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    5
    Tags
    # Submissions
    18
    Accepted
    5
    Uploaded By