closefrom

思路

见题意，由于每次只向四个方向尝试移动，所以可采用深搜（状态为坐标）。

然而数据规模中，n<=1000，m<=100000，如果每次输入坐标时重新走一次将会超时。

再想想，每一次搜索会找到一个区块，该区块中所有点的答案都相同，所以，答案可以存在一个数组里——

题目每给出一个坐标，先判断该坐标是否已有答案（通过前面已给出的点搜索获得的），是则直接输出，否则深搜：先重置pl，为了将该点所属区块都染上色（不能在深搜内部染色，因为过程中并不知道区域内到底有多少连通点），在一趟深搜过程中，每到一个新的点就++pl，并将该点的坐标存在临时数组里，搜索结束后再依据坐标数组把答案数组的对应位置填上pl。

//my ac code
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int n,ans,m;
int ng[1005][1005];
int nn[1005][1005];
int jg[1000005][2];
int x[4]={1,0,-1,0};
int y[4]={0,-1,0,1};
void dfs(int a,int b){
    ans++;
    jg[ans][0]=a;
    jg[ans][1]=b;
    nn[a][b]=1;
    for(int i=0;i<4;i++){
        int xa=a+x[i];int ya=b+y[i];
        if(xa<1||xa>n||ya<1||ya>n)continue;
        if(nn[xa][ya]>0)continue;
        if(ng[a][b]==ng[xa][ya])continue;
        dfs(xa,ya);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    //printf("%d%d",n,m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%1d",&ng[i][j]);
            //printf("%1d",ng[i][j]);
        }
        //printf("\n");
    }
            
    for(int i=1;i<=m;i++){
        ans=0;
        int tx,ty;
        scanf("%d%d",&tx,&ty);
        if(nn[tx][ty]>0){
            printf("%d\n",nn[tx][ty]);
            continue;
        }
        dfs(tx,ty);
        for(int j=1;j<=ans;j++)
            nn[jg[j][0]][jg[j][1]]=ans;
        printf("%d\n",ans);
    }
    return 0;
}