1 solutions
-
0
#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