来自一只菜鸡的怒吼
本人萌新一只，这道题在AC之前交了35遍，做了三天，中间夹杂着做了两道题，深有感触啊啊啊啊！！应该是踩了一遍所有的坑，所以发篇题解纪念一下！（我会告诉你们我因为过了这道题在家疯狂拍桌子然后出去吃了顿火锅纪念一下？？）
比较菜所以用的最简单的bfs。理所当然的三个点都超时。（因为数组开的不够大还有两个是错的）
文中的wb，tp都是自己的好老师哈哈哈，每次害怕自己的变量在循环中重复就会出现他俩的名字呢哈哈哈。
这里w，b用来判断前后位置是否字符不相同，也就是0或1。 xx yy两个队列用来储存搜索点的坐标。 map数组储存了整张地图。 book数组标记点是否到达过，这里它是不用多次重置的，因为联通块的思想就是当我一整块搜索完了之后他们中的成员就不用第二次搜索，从而提高效率。 step就用来储存每个点能到达多少个点啦~~ inx，iny就用来储存在搜索中，每一个联通块中的每个成员。
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<iostream>
using namespace std;
queue<int >xx;
queue<int >yy;
char w,b;
char map[1001][1001];
int book[1001][1001]={};
int step[1001][1001]={};
int inx[1001]={};
int iny[1001]={};
int n,m;
int sum=1;
int bfs(int ,int );
int i,j;
int main()
{
scanf("%d%d",&n,&m);
for(int t=1;t<=n;t++)
{
for(int p=1;p<=n;p++)
cin >> map[t][p];
}
for(int t=1;t<=m;t++)
{
scanf("%d%d",&inx[t],&iny[t]);
}
for(int b=1;b<=m;b++)
{
for(int w=1;w<=1000;w++)
for(int b=1;b<=1000;b++)
{
book[w][b]=0;
step[w][b]=0;
sum=1;
}
xx.push(inx[b]);
yy.push(iny[b]);
printf("%d\n",bfs(inx[b],iny[b]));
}
getchar();
getchar();
return 0;
}
int bfs(int x,int y)
{
int move[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
book[x][y]=1;
int nx,ny;
while(xx.size()!=0 && yy.size()!=0)
{
xx.pop();
yy.pop();
for(int t=0;t<4;t++)
{
nx=x+move[t][0];
ny=y+move[t][1];
w=map[x][y];
b=map[nx][ny];
if(book[nx][ny]==0 && w!=b && nx>0 && ny>0 && nx<=n && ny<=n)
{
sum++;
book[nx][ny]=1;
step[nx][ny]=step[x][y]+1;
xx.push(nx);
yy.push(ny);
}
}
x=xx.front();
y=yy.front();
}
return sum;
}
之后的两天就疯狂查错，发现是自己inx，iny数组开的过于小，应该开到m的范围也就是100000。 并且为了提高性能加入联通块这个思想。 即在进行bfs的过程中，对于每一个搜索到的点都记录，搜索结束之后，刚刚记录的所有点可到达的位置都相同。 举个例子： 一个池塘里，在任意一点放入一条鱼，它可以游到的位置是整个池塘，无论你选择从东边放入还是西边，是从正中间还是某一个对你有特殊意义的点。
还没理解也没关系，例子多得是： 你想去认识学校中所有的大佬，你需要从你的班级去到整个学校所有的班级，如果我们并不关注路径过程，结果一定是你去到了所有年级的所有班级，但无论你是小学三年级还是初中三年级亦或是高三年级，你都会去到每一个班里。 联通块如果各位看完还是不能理解的话，作为菜鸡确实找不到什么更形象的例子了，麻烦各位移步百度。 然后附上AC代码，里面会再次解释。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<iostream>
using namespace std;
queue<int >xx;
queue<int >yy;
char w,b;
char map[1001][1001];
int book[1001][1001]={};
int step[1001][1001]={};
int in[1000001][3];
int inx;
int iny;
int n,m;
int bfs(int ,int );
int i,j;
int main()
{
scanf("%d%d",&n,&m);
for(int t=1;t<=n;t++)
{
for(int p=1;p<=n;p++)
cin >> map[t][p];
}//注意：这里读入我也调试了超级久
//好像因为洛谷的原因
//如果使用scanf（%c）用getchar（）；吸收字符的时候会出现一些些问题，
/*for(int t=1;t<=n;t++)
{
for(int p=1;p<=n;p++)
printf("%c",map[t][p]);
printf("\n");
}*/
//这个注释用来看看自己的map到底有没有输对，毕竟只有地图对了才有可能做题，地图上我就查了一天，要不是有大佬告诉我getchar（）不好使，我可能会和scanf（）对刚一整天
for(int t=1;t<=m;t++)
{
scanf("%d%d",&inx,&iny);
if(book[inx][iny]==0)
{
bfs(inx,iny);
printf("%d\n",step[inx][iny]);
}
else
{
printf("%d\n",step[inx][iny]);
}
//这里发现可以读一个查一个，于是就没有再用整个数组存进来然后重头再扫一次。
}
getchar();
getchar();
return 0;
}
int bfs(int x,int y)
//咳咳！这里是折腾我最久的地方了
{
int flag=1;
//flag是因为实在想不到别的好的变量名去存可以到的地点的个数，后来发现flag貌似和sum一样
int nx,ny;
int move[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int sum=1;
in[flag][1]=x;
in[flag][2]=y;
book[x][y]=1;
xx.push(x);
yy.push(y);
//这里一定要记得标记起点和将起点的坐标放进队列，这里也看了好久才发现。
while(xx.size()!=0 && yy.size()!=0)
{
xx.pop();
yy.pop();
for(int t=0;t<4;t++)
{
nx=x+move[t][0];
ny=y+move[t][1];
w=map[x][y];
b=map[nx][ny];
if(book[nx][ny]==0 && w!=b && nx>0 && ny>0 && nx<=n && ny<=n)
{
flag++;
in[flag][1]=nx;
in[flag][2]=ny;
book[nx][ny]=1;
xx.push(nx);
yy.push(ny);
sum++;
}
}
x=xx.front();
y=yy.front();
}
//上面都是简单的bfs，但是记得过程中要记录每一个能到的点。这里的book是不用重置的哦。
for(int u=1;u<=flag;u++)
{
step[in[u][1]][in[u][2]]=sum;
}
//再将每一个成员能到的点的个数分别记录下来！他们能到的个数都一样哦~~
return sum;
}
整篇完结！ 代码习惯不太好各位见谅，表述不清各位也多多包涵，如果真的看不懂可以看看其他大佬的题解，说的都超级简单易懂。