这道题可以用DFS，也可以用BFS，这里我采用了DFS（因为懒）。
题目大意
给定一个只含000和111、n×nn times nn×n的迷宫：
代码语言：javascript复制n=4
1 0 0 1
1 1 0 0
0 1 1 0
1 0 0 1从每一个为000的位置，可以走到相邻的111处；从每一个为111的位置，可以走到相邻的000处。即上一个走过来的格子不能与现在的格子相同。
接下来有mmm次查询，每次查询给定一个x,yx,yx,y，表示迷宫里第xxx行第yyy列的格子，询问从这里开始最多能走到几个格子（包括自身）。
做法
普通DFS
根据题意，很容易得到第一版的DFS代码：
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
bool Map[1005][1005];
int mapBooker[1005][1005];
int n,m;
int search(int x,int y,bool last){
/*判定是否越界、已经搜索过*/
if(last==Map[x][y] or x<1 or x>n or y<1 or y>n or !mapBooker[x][y])return 0;
mapBooker[x][y]=1;//标记
return search(x-1,y,id,Map[x][y]) search(x 1,y,id,Map[x][y]) search(x,y 1,id,Map[x][y]) search(x,y-1,id,Map[x][y]) 1;//继续搜索，搜索周围四个点，同时算上自己
}
int main(){
char tmp;
std::ios::sync_with_stdio(false);
cin.tie(0);//加快cin的读入
cin>>n>>m;
for(int i=1;i<=n;i ){
for(int j=1;j<=n;j ){
cin>>tmp;
Map[i][j]=(tmp=='0'?false:true);
}
}
int x,y;
for(int i=1;i<=m;i ){
memset(mapBooker,0,sizeof(mapBooker));//清空标记数组
cin>>x>>y;
cout<<search(x,y,!Map[x][y])<<endl;
}
}但这样的代码只拿了70分，剩下的三个点全部超时。
DFS 联通块
我们可以发现，在同一个块里的点都能相互联通，所以，只要这一个块里的其中一个点被搜过了，其它的点其实已经得出来了：
在上图，红框框起来的点都可以互相到达，所以他们最多能走到的格子都一样，即这个联通块内的坐标个数——777个。
这样，可以得出第二版代码：
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
bool Map[1005][1005];
int mapBooker[1005][1005];
int answerQueue[100005];
int n,m;
int search(int x,int y,int id,bool last){
/*判定是否越界、已经搜索过*/
if(last==Map[x][y] or x<1 or x>n or y<1 or y>n or mapBooker[x][y]!=-1)return 0;
mapBooker[x][y]=id;//标记联通块编号
return answerQueue[id]=search(x-1,y,id,Map[x][y]) search(x 1,y,id,Map[x][y]) search(x,y 1,id,Map[x][y]) search(x,y-1,id,Map[x][y]) 1;//搜索，同时将答案放入答案区
}
int main(){
char tmp;
std::ios::sync_with_stdio(false);
cin.tie(0);
memset(mapBooker,-1,sizeof(mapBooker));
cin>>n>>m;
for(int i=1;i<=n;i ){
for(int j=1;j<=n;j ){
cin>>tmp;
Map[i][j]=(tmp=='0'?false:true);
}
}
int x,y;
for(int i=1;i<=m;i ){
cin>>x>>y;
if(mapBooker[x][y]!=-1){//已经被搜过了
cout<<answerQueue[mapBooker[x][y]]<<endl;
}
else cout<<search(x,y,i,!Map[x][y])<<endl;
}
}由于联通块的特性，我们不需要每次都清空mapBooker数组，因为只要搜过的地方就没必要再搜了。
再次提交，成功AC。
