@[ztx666](/space/show?uid=125018) 同一联通块的$ans$一定相同,所以加个记忆化就好了
by zl_just @ 2019-05-11 19:36:27
@[ztx666](/space/show?uid=125018) 好吧,没看仔细,我用记忆化过了,爱莫能助 (尬
by zl_just @ 2019-05-11 19:37:58
@[ztx666](/space/show?uid=125018) 标记同一联通块就好了
```cpp
#include<cstdio>
#include<cstring>
#define ww 1000
char s[1010][1010];
int way[1010][1010];
int ans[1000000+10];
bool vis[1010][1010]={0};
int n,x1,y1,num;
int dx[]={-1,0,0,1};
int dy[]={0,-1,1,0};
void dfs(int x,int y,int mark,int &S) {
if(x<0||y<0||x>=n||y>=n||s[x][y]!=mark+'0'||vis[x][y]) return;
vis[x][y]=true;
way[x][y]=num;
S++;
for(int i=0;i<4;i++)
dfs(x+dx[i],y+dy[i],!mark,S);
}
int main()
{
int m;
memset(way,0,sizeof(way));
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++) scanf("%s",s[i]);
while(m--) {
scanf("%d%d",&x1,&y1);
x1--; y1--;
if(!way[x1][y1]) {
int sum=0;
way[x1][y1]=++num;
dfs(x1,y1,s[x1][y1]-'0',sum);
ans[num]=sum;
}
printf("%d\n",ans[way[x1][y1]]);
}
return 0;
}
```
by zl_just @ 2019-05-11 19:39:49
tks
by ztx__ @ 2019-10-03 14:49:32
感谢大佬
by ztx__ @ 2019-10-03 14:49:44