_X_Z_N_ @ 2024-10-09 22:22:40
rt,但是不知道哪里写错了
写的是连通块做法
#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;
}