题目链接

dfs预处理求出联通块,然后根据题目的要求可以得到所有联通块内格子答案都相同。

#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
using namespace std;
inline int read()
{
    int neg=1,x=0;
    char ch;
    while((ch=getchar())<'0'||ch>'9')
        if(ch=='-')
            neg=-1;
    x=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')
        x=x*10+(ch-'0');
    return x*neg;
}
queue< pair<int,int> > q;
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
int n,m,ans,tot;
int dn[1005][1005],tu[1005][1005];
bool vis[1005][1005];
inline void clear(queue< pair<int,int> > &q)
{
    queue< pair<int,int> > empty;
    swap(empty,q);
}
inline void dfs(int x,int y)
{
    for(register int i=0;i<4;i++)
    {
        int lx=x+dx[i];
        int ly=y+dy[i];
        if(lx<=n&&ly<=n&&lx>=1&&ly>=1&&(vis[lx][ly]==false)&&(tu[lx][ly]!=tu[x][y]))
        {
            vis[lx][ly]=true;
            tot++;
            dfs(lx,ly);
            q.push(make_pair(lx,ly));
        }
    }
}
int main()
{
    memset(vis,false,sizeof(vis));
    n=read(),m=read();
    for(register int i=1;i<=n;i++)
    {
        for(register int j=1;j<=n;j++)
        {
            dn[i][j]=1;
            scanf("%1d",&tu[i][j]);
        }
    }
    for(register int i=1;i<=n;i++)
        for(register int j=1;j<=n;j++)
        {
            tot=1;
            if(!vis[i][j])
            {
                vis[i][j]=true;
                dfs(i,j);
                q.push(make_pair(i,j));
            }
            while(q.size())
            {
                dn[q.front().first][q.front().second]=tot;
                q.pop();
            }
        }
    int q1,q2;
    for(register int i=1;i<=m;i++)
    {
        q1=read(),q2=read();
        printf("%d\n",dn[q1][q2]);
    }
    return 0;
}