【洛谷 P1141】01迷宫
这道题可以用DFS，也可以用BFS，这里我采用了DFS（因为懒）。
题目大意
给定一个只含000和111、n×nn \times nn×n的迷宫：
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代码：
#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分，剩下的三个点全部超时。
image.png
DFS+联通块
我们可以发现，在同一个块里的点都能相互联通，所以，只要这一个块里的其中一个点被搜过了，其它的点其实已经得出来了：
image.png
在上图，红框框起来的点都可以互相到达，所以他们最多能走到的格子都一样，即这个联通块内的坐标个数——777个。
这样，可以得出第二版代码：
#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。
image.png
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021-10-13，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录