GB2312 @ 2024-09-23 21:21:12
rt
bfs并查集计数除了hack全部WA
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m,i,j,k,nowx,nowy;
int fx[4]={0,0,1,-1};
int fy[4]={1,-1,0,0};
bool a[N][N],vis[N][N];
char s;
struct point
{
int x,y;
friend bool operator ==(point p,point q)
{
return (p.x==q.x&&p.y==q.y);
}
friend bool operator <(point p,point q)
{
return p.x<q.x;
}
}now,tmp,vising;
map<point,point> fa;
map<point,int> cnt;
queue<point> q;
point find(point p)
{
if(p==fa[p]) return p;
return fa[p]=find(fa[p]);
}
int main()
{
cin>>n>>m;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cin>>s;
a[i][j]=(s-'0');
tmp.x=i,tmp.y=j;
fa[tmp]=tmp;
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(!vis[i][j])
{
vising.x=i,vising.y=j;
q.push(vising);
while(!q.empty())
{
now=q.front();q.pop();
nowx=now.x,nowy=now.y;
fa[now]=vising;
if(!vis[nowx][nowy])
{
vis[nowx][nowy]=1;
for(k=0;k<4;k++)
{
tmp.x=nowx+fx[k],tmp.y=nowy+fy[k];
if(tmp.x>0&&tmp.x<=n&&tmp.y>0&&tmp.y<=n) q.push(tmp);
}
}
}
}
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
tmp.x=i,tmp.y=j;
tmp=find(tmp);
cnt[tmp]++;
}
}
while(m--)
{
cin>>i>>j;
tmp.x=i,tmp.y=j;
tmp=find(tmp);
cout<<cnt[tmp]<<'\n';
}
return 0;
}
by naijgnorgnahz @ 2024-09-23 21:55:11
@GB2312 不是你不能应付啊,应付不对map不给你好好工作啊
by GB2312 @ 2024-09-23 22:10:02
@naijgnorgnahz
friend bool operator <(point p,point q)
{
return ((p.x==q.x)?(p.x<q.x):(p.y<q.y));
}
改完之后记录
by naijgnorgnahz @ 2024-09-23 22:17:10
要不你考虑把struct换掉?
by GB2312 @ 2024-09-23 22:23:17
@naijgnorgnahz 拿pair行吗
by naijgnorgnahz @ 2024-09-23 22:24:22
@GB2312 我在读入的for后面查询了fa[(1,1)]的值,显示值为(2,1)
by naijgnorgnahz @ 2024-09-23 22:25:05
应该是你出了奇怪的错误
by naijgnorgnahz @ 2024-09-23 22:25:38
pair应该行
by naijgnorgnahz @ 2024-09-23 22:25:50
run了,再见
by GB2312 @ 2024-09-23 22:29:47
@naijgnorgnahz ok谢谢神犇