xiaotaiji @ 2024-03-03 12:48:04
#include <bits/stdc++.h>
using namespace std;
string s[1000];
int n,m,ans,k;//ans是计算某个连通分量的个数,k计算有多少个连通分量
int vis[1000][1000];//看他是否已经被划分到某个连通分量中
int num[1000];//存储k个连通分量的个数
int di[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
void dfs(int x,int y)
{
int i,newx,newy;
vis[x][y]=k;//把(x,y)划入第k个连通分量中
ans++;
for(i=0;i<4;i++)
{
newx=x+di[i][0];
newy=y+di[i][1];
if(newx>=0&&newx<n&&newy>=0&&newy<n&&vis[newx][newy]==0)
{
if(s[x][y]!=s[newx][newy])
dfs(newx,newy);
}
}
}
int main()
{
int i,x,y;
cin>>n>>m;
for(i=0;i<n;i++)
cin>>s[i];
k=1;//连通分量从1开始计数
memset(vis,0,sizeof(vis));
for(i=0;i<m;i++)
{
cin>>x>>y;
ans=0;
x--;y--;
if(vis[x][y]==0)//若被划入连通分量,就直接输出,否则,进入dfs找
{
dfs(x,y);
num[k]=ans;
k++;
cout<<ans<<endl;
}
else cout<<num[vis[x][y]]<<endl;
}
return 0;
}