Greeper @ 2024-12-14 19:25:11
#include<bits/stdc++.h>
using namespace std;
bool a[1005][1005];
bool f[1005][1005];
int nu[1005][1005];
int n,m,ii,jj;
int gx[4]={0,1,0,-1},gy[4]={1,0,-1,0};
int bfs()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
f[i][j]=0;
}
}
if(nu[ii][jj])
{
return nu[ii][jj];
}
int num=1;
queue<int> x;
queue<int> y;
f[ii][jj]=1;
x.push(ii);
y.push(jj);
while(!x.empty())
{
int nx=x.front(),ny=y.front();
x.pop();y.pop();
for(int i=0;i<4;i++)
{
int tx=nx+gx[i],ty=ny+gy[i];
if(tx>=1&&tx<=n&&ty>=1&&ty<=n)
{
if(!f[tx][ty]&&a[nx][ny]!=a[tx][ty])
{
f[tx][ty]=1;
num++;
x.push(tx);
y.push(ty);
}
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(f[i][j])
{
nu[i][j]=num;
}
}
}
return num;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%1d",&a[i][j]);
}
}
while(m--)
{
cin>>ii>>jj;
cout<<bfs()<<endl;
}
return 0;
}by CZX_HWH @ 2024-12-14 20:57:27
@Greeper 试一下吧
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int n,m,vis[N][N],cnt,s[N*N];
char mp[N][N];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
void DFS(int x,int y)
{
if(x<1||y<1||x>n||y>n)
{
return;
}
if(vis[x][y]>0)
{
return;
}
vis[x][y] = cnt,s[cnt]++;
for(int i=0;i<4;i++)
{
if(mp[x][y]!=mp[x+dx[i]][y+dy[i]])
{
DFS(x+dx[i],y+dy[i]);
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>mp[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(vis[i][j]==0)
{
cnt++,DFS(i,j);
}
}
}
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
cout<<s[vis[x][y]]<<endl;
}
return 0;
}