【洛谷 P1141】01迷宫

pai233

发布于 2022-01-12 17:04:40

4850

发布于 2022-01-12 17:04:40

文章被收录于专栏：pai233的专栏

这道题可以用DFS，也可以用BFS，这里我采用了DFS（因为懒）。

题目大意

给定一个只含000和111、n×nn \times nn×n的迷宫：

从每一个为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分，剩下的三个点全部超时。

DFS+联通块

我们可以发现，在同一个块里的点都能相互联通，所以，只要这一个块里的其中一个点被搜过了，其它的点其实已经得出来了：

在上图，红框框起来的点都可以互相到达，所以他们最多能走到的格子都一样，即这个联通块内的坐标个数——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。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021-10-13，如有侵权请联系 cloudcommunity@tencent.com 删除

dfs

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

dfs

登录后参与评论

0 条评论

热度