社区讨论
听灌多,救救蒟蒻吧
灌水区参与者 3已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @m21yt8me
- 此快照首次捕获于
- 2024/10/09 22:28 去年
- 此快照最后确认于
- 2025/11/04 17:32 4 个月前
有4个点WA掉了,但是不知道是哪出问题了
代码:
CPP#include<bits/stdc++.h>
using namespace std;
bool ph[1005][1005];//01图
int num=1;//统计染色编号、联通块个数
int ans[1005];//编号为i的联通块的大小为ans[i]
int pp[1005][1005];//染色图
void dfs(int x,int y)//搜联通
{
ans[pp[x][y]]++;
if(ph[x][y]!=ph[x+1][y] && pp[x+1][y]==0)
{
pp[x+1][y]=pp[x][y];
dfs(x+1,y);
}
if(ph[x][y]!=ph[x-1][y] && pp[x-1][y]==0)
{
pp[x-1][y]=pp[x][y];
//ans[pp[x][y]]++;
dfs(x-1,y);
}
if(ph[x][y]!=ph[x][y+1] && pp[x][y+1]==0)
{
pp[x][y+1]=pp[x][y];
//ans[pp[x][y]]++;
dfs(x,y+1);
}
if(ph[x][y]!=ph[x][y-1] && pp[x][y-1]==0)
{
pp[x][y-1]=pp[x][y];
//ans[pp[x][y]]++;
dfs(x,y-1);
}
}
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
char c;
cin>>c;
if(c=='0')
{
ph[i][j]=0;
}
else
{
ph[i][j]=1;
}
}
pp[0][i]=-1;
pp[i][0]=-1;
pp[n+1][i]=-1;
pp[i][n+1]=-1;//边界为-1
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(pp[i][j]==0)//未搜索过的编号为0
{
pp[i][j]=num++;//使用新编号
dfs(i,j);
}
//cout<<pp[i][j]<<" "<<i<<" "<<j<<" "<<ans[pp[i][j]]<<endl;
}
}
while(m--)
{
int a,b;
cin>>a>>b;
cout<<ans[pp[a][b]]<<endl;//出答案
}
return 0;
}
写的是dfs染色的做法
帮帮蒟蒻吧
回复
共 4 条回复,欢迎继续交流。
正在加载回复...