C++(g++ 7.5.0) 解法, 执行用时: 563ms, 内存消耗: 49280K, 提交时间: 2023-04-07 20:58:39

#include<bits/stdc++.h>
using namespace std;
int n,m,q,w,cnt;
char a[3010][3010];
int s[3010][3010];
int v[9100010];
int d[4][2]={1,0,0,1,-1,0,0,-1};
void dfs(int x,int y)
{
    v[cnt]++;
    s[x][y]=cnt;
    for(int i=0;i<4;i++)
    {
        int dx=x+d[i][0];
        int dy=y+d[i][1];
        if(a[dx][dy]!=a[x][y]&&dx>=0&&dx<n&&dy>=0&&dy<m&&!s[dx][dy])
            dfs(dx,dy);
    }
}

int main()
{
    cin>>n>>m>>q;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
               if(!s[i][j])
                   cnt++,dfs(i,j);
    while(q--)
    {
        int x,y;
        cin>>x>>y;
        cout<<v[s[x-1][y-1]]<<endl;
    }
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 383ms, 内存消耗: 84344K, 提交时间: 2020-08-23 14:01:19

#include<cstdio>
using namespace std;
const int maxn=3003;
int n,m,q,tot=0;
int sz[maxn*maxn],cnt[maxn][maxn],vis[maxn][maxn];
char a[maxn][maxn];
int d[4][2]={1,0,-1,0,0,1,0,-1};
void dfs(int x,int y,int z){
	vis[x][y]=1;
	++sz[tot];
	cnt[x][y]=z;
	for(int i=0;i<4;++i){
		int a1=x+d[i][0],b1=y+d[i][1];
		if(!vis[a1][b1]&&a1>=1&&a1<=n&&b1>=1&&b1<=m&&a[a1][b1]!=a[x][y])
			dfs(a1,b1,z);
	} 
}
int main(){
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;++i)
		scanf("%s",a[i]+1);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			if(!vis[i][j])
				dfs(i,j,++tot);
	while(q--){
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%d\n",sz[cnt[x][y]]);
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 416ms, 内存消耗: 49516K, 提交时间: 2020-06-19 12:58:33

#include<bits/stdc++.h>
using namespace std;

int n,m,q,ans[9000005]={0},T[3005][3005]={0};
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
char R[3005][3005];
void DFS(int x,int y,int z)
{
	int i,X,Y;
	for(i=0;i<4;i++)
	{
		X=x+dx[i],Y=y+dy[i];
		if(X<0||X>=n||Y<0||Y>=m||T[X][Y]||R[x][y]==R[X][Y])continue;
		T[X][Y]=z,ans[z]++,DFS(X,Y,z);
	}
} 
int main()
{
    int i,j,t=0;
    scanf("%d%d%d",&n,&m,&q);
    for(i=0;i<n;i++)scanf("%s",R[i]);
    for(i=0;i<n;i++)
        for(j=0;j<m;j++)if(!T[i][j])T[i][j]=++t,ans[t]++,DFS(i,j,t);
	while(q--)
	{
		scanf("%d%d",&i,&j);
		printf("%d\n",ans[T[i-1][j-1]]);
	}
}