@[DeepWhite_](/space/show?uid=184404)
dfs应该这么写。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N=1234;
const int MAXN=123456;
const int INF=1234567;
int tot[INF],m,n,cnt,a[N][N],vis[N][N],val[N][N],x[MAXN],y[MAXN];
char s[N];
void dfs(int x,int y,int cnt)
{
if(vis[x][y])
return;
a[x][y]=cnt;
vis[x][y]=1;
tot[cnt]++;
if(x>1&&val[x-1][y]==val[x][y])dfs(x-1,y,cnt);
if(y>1&&val[x][y-1]==val[x][y])dfs(x,y-1,cnt);
if(x<n&&val[x+1][y]==val[x][y])dfs(x+1,y,cnt);
if(y<n&&val[x][y+1]==val[x][y])dfs(x,y+1,cnt);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%s",s+1);
for(int j=1;j<=n;j++)
val[i][j]=s[j]-'0'^(i+j&1);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(!a[i][j])cnt++;
dfs(i,j,cnt);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x[i],&y[i]);
printf("%d\n",tot[a[x[i]][y[i]]]);
}
return 0;
}
```
by Smile_Cindy @ 2019-03-19 21:29:56
@[DeepWhite_](/space/show?uid=184404) 这题必须记忆化DFS/BFS，不然就TLE
by wxwoo @ 2019-03-19 21:37:11
~~论cache的重要性~~
by fzfnf @ 2019-03-19 21:38:34
@[wxwoo](/space/show?uid=116659) 这算记忆化么？
```cpp
#include<cstdio>
using namespace std;
int n,m,i,j,x,y,s,t=1,f[4][2]={{0,1},{1,0},{0,-1},{-1,0}},a[1001][1001],b[1001][1001],g[100001]; char c[1001];
void dfs(int x,int y)//未改动
{
b[x][y]=t;
for(int k=0;k<=3;k++)
{
int tx=x+f[k][0],ty=y+f[k][1];
if(!(tx<1||tx>n||ty<1||ty>n||b[tx][ty]==t||a[tx][ty]==a[x][y]))
{
s++; b[tx][ty]=t;
dfs(tx,ty);
}
}
return ;
}
int main()
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%s",c);
for(j=1;j<=n;j++)
a[i][j]=c[j-1]-'0';
}
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
if(b[x][y]!=0)
{
printf("%d",g[b[x][y]]); continue;//如果走过了就输出存在g数组里的s
}
dfs(x,y);
printf("%d\n",s+1);
g[i]=s+1; s=0; t++;//每次把s放进g数组存储
}
return 0;
}
```
by Naivecat是女孩子 @ 2019-03-19 21:42:33
先找联通块，再直接输出
by AC_Automation @ 2019-03-19 21:42:34
@[DeepWhite_](/space/show?uid=184404)
~~并查集多好用~~
by nofall @ 2019-03-19 21:43:14
@[咕咕咕自动机](/space/show?uid=118317) qaq
by Naivecat是女孩子 @ 2019-03-19 21:45:58
用LCA
by Anonymous匿名者 @ 2019-03-19 22:04:44
当我没说
by Anonymous匿名者 @ 2019-03-19 22:05:07
@[DeepWhite_](/space/show?uid=184404) 算
by wxwoo @ 2019-03-19 22:07:16