题解 P7225 【[RC-04] 走迷宫】

· · 题解

题意简述：

通过 交互 模拟走迷宫从而获得一个满足某些性质的迷宫的地图。

也就是探索迷宫啦。

有点像 level13

题目解法：

不颓废了，开始讲正解。

这个 \rm dfs 走 确定 迷宫应该大家都会吧。

不会有关系，因为您听不懂我在说什么。

然后就模拟 \rm dfs 走迷宫就行了。

每步往四个方向都探索一下，直到碰壁返回。

然后就是注意不要走回头路。

具体见代码，不然会因步数过多 \color{red}\rm WA。

正确代码：

#include<bits/stdc++.h>
using namespace std;
extern "C" bool move_to(char position);
int dta[505][505];
const int dx[]={-1,0,1,0},dy[]={0,-1,0,1};
const char ch[]={'W','A','S','D'};
void dfs(int x,int y){
    dta[x][y]=1;
    for(register int i=0;i<4;++i){
        int xx=x+dx[i],yy=y+dy[i];
        if(~dta[xx][yy]){
            continue;
        }
        bool tmp=move_to(ch[i]);
        if(!tmp){
            dta[xx][yy]=0;
            continue;
        }
        dfs(xx,yy);
        if(i&1)move_to(ch[4-i]);
        else move_to(ch[2-i]);
    }
    return;
}
extern "C" string find_out_map(int x,int y,int n){
    memset(dta,-1,sizeof(dta));
    dfs(x,y);
    std::string ans="";
    for(register int i=1;i<=n;++i){
        for(register int j=1;j<=n;++j){
            if(dta[i][j]==1)ans+='0';
            else ans+='1';
        }
    }
    return ans;
}

如果您没有看懂这篇题解，可以在评论区问我，我将会回答您的问题并且修改这篇题解，使它变得更加通俗易懂，服务更多的 \text{OIer}。
如果您看懂了这篇题解，可以点个赞，使这篇题解的排名上升，服务更多的 \text{OIer}。