社区讨论
求教,并查集+DFS怎么改
P114101迷宫参与者 3已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @mi7xakvk
- 此快照首次捕获于
- 2025/11/21 05:07 4 个月前
- 此快照最后确认于
- 2025/11/21 05:07 4 个月前
CPP
#include <cstdio>
#include <utility>
#include <map>
#define pii std::pair<int,int>
#define mkpii(a,b) std::make_pair((a),(b))
const int dx[4]= {0,0,1,-1},dy[4]= {1,-1,0,0};
int n,maps[1005][1005];
bool done[1005][1005];
std::map<pii,pii>f;
std::map<pii,int>value;
pii find(pii a)
{
return f[a]==a?a:f[a]=find(f[a]);
}
void hb(pii a,pii b)
{
pii fa=find(a),fb=find(b);
if (fa!=fb) f[fb]=fa;
return;
}
void dfs(int x,int y)
{
done[x][y]=true;
for (int i=0; i<4; i++)
if (!done[x+dx[i]][y+dy[i]]&&maps[x][y]+maps[x+dx[i]][y+dy[i]]==1)
hb(mkpii(x,y),mkpii(x+dx[i],y+dy[i])),
dfs(x+dx[i],y+dy[i]);
}
int main()
{
int a,b,m,sum;
scanf("%d%d",&n,&m);
int sss[n+2][n+2];
for (int i=1; i<=n; ++i)
for (int j=1; j<=n; ++j)
scanf("%1d",&sss[i][j]),
f[mkpii(i,j)]=mkpii(i,j);
while (m--)
{
sum=0;
for (int i=1; i<=n; ++i)
for (int j=1; j<=n; ++j)
done[i][j]=false,
maps[i][j]=sss[i][j];
scanf("%d%d",&a,&b);
dfs(a,b);
if (find(mkpii(a,b))==mkpii(a,b))
{
for (int i=1; i<=n; ++i)
for (int j=1; j<=n; ++j)
if (done[i][j])
++sum;
value[find(mkpii(a,b))]=sum;
}
printf("%d\n",value[find(mkpii(a,b))]);
}
return 0;
}
回复
共 4 条回复,欢迎继续交流。
正在加载回复...