首页 » 技术分享 » 神奇怪兽在哪里 DFS

神奇怪兽在哪里 DFS

　
评论关闭　526次浏览

神奇怪兽在哪里

原题链接
单点时限: 2.0 sec

内存限制: 256 MB

熊猫先生最近在玩一款单机游戏。

在游戏中，会有一张 n 行 m 列的地图（如样例中所示）。用 . 表示空地，用 * 表示怪兽，用 P 表示熊猫先生现在所在的位置。怪兽只有一个，所以由 * 组成的块一定是一个上下左右四连通块。游戏的规则是：熊猫先生要把怪兽「包住」，并且回到现在所在的位置，才能把怪兽消灭掉。

「包住」的含义是：走过的路径可以将怪兽封闭起来。只能在空地上行走。走过的路径可以相交，可以重叠，可以重复走，只要围住就好了。

由于这是一款在命令行下运行的复古单机游戏，熊猫先生只能按上下左右四个键，即他只能向上下左右四个方向移动。你能找到一种消灭怪兽的方法吗？

输入格式

输入包含多个测试文件，每个测试文件是单组测试数据。

第一行两个整数 n,m (1≤n,m≤100)。对于 30% 的数据，满足：1≤n,m≤20。

接下来 n 行，每行一个长度为 m 的字符串，表示地图。

. 表示空地，* 表示怪兽，P 表示熊猫先生现在所在的位置。输入保证熊猫先生不会出现在「怪兽里面」。

输出格式

输出一行，一个字符串，表示要消灭怪兽所要执行的操作序列：

向上走用 U 表示；
向下走用 D 表示；
向左走用 L 表示；
向右走用 R 表示。
输入保证有解。输出任意一解即可。在这里插入图片描述在这里插入图片描述

分析:

看标签是典型的dfs题,却卡了好大一会儿,最后终于想明白了;

dfs的本质是一种遍历/搜索方式,如果不加终止条件,它一般用来回溯得到所有可能情况.
如果设置搜索标志位flag,那么可以在dfs的中途退出,得到其中一种结果.

本题相对于传统的dfs,难点在于可以重复经过,并且最后还要找到回来的路,还要包住其中指定的图案.
最大外框必定可以包住指定图案,此外我们只需要前后各进行一次从起点到终点的路径dfs,即可找到合理路径.

1. 从p点到(0,0)dfs
2. 从(0,0)到(0,0)环绕一周
3. 从(0,0)到p点dfs

代码实现:

#include<bits/stdc++.h>
using namespace std;
const int dx[4]={0,0,-1,1};
const int dy[4]={-1,1,0,0};
char str[101][101];
bool vis[101][101];
int m,n,px,py;
bool flag;
vector<char>path;//回溯保存路径
bool inMaze(int x,int y)//在地图内
{
    return x>=0&&x<n&&y>=0&&y<m;
}
void dfs(int x,int y,int endx,int endy,vector<char> &path)
{
    if(flag)//已找到路径
        return;
    if(x==endx&&y==endy)//终止条件
    {
        flag=1;
        for(int i=0;i<path.size();i++)//print路径
            cout<<path[i];
        return;
    }
    for(int i=0;i<4;i++)
    {
        int newx=x+dx[i];
        int newy=y+dy[i];
        if(inMaze(newx,newy)&&str[newx][newy]!='*'&&!vis[newx][newy])
        {
            if(i==0)
                path.push_back('L');
            if(i==1)
                path.push_back('R');
            if(i==2)
                path.push_back('U');
            if(i==3)
                path.push_back('D');
            vis[newx][newy]=1;
            dfs(newx,newy,endx,endy,path);
            path.pop_back();//回溯(两次dfs不用更新path,path元素在每次dfs在结束返回时逐个popback直至clear)
            vis[newx][newy]=1;
        }
    }
}
int main()
{
    while(cin>>n>>m)
    {
        for(int i=0;i<n;i++)
            scanf("%s",str[i]);//输入

        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
                if(str[i][j]=='P')
                px=i,py=j;//记录位置
        }

        memset(vis,0,sizeof(vis));//第一次寻路
        flag=0;
        vis[px][py]=1;
        dfs(px,py,0,0,path);

        for(int i=0;i<n-1;i++)//环绕
            cout<<"D";
        for(int i=0;i<m-1;i++)
            cout<<"R";
        for(int i=0;i<n-1;i++)
            cout<<"U";
        for(int i=0;i<m-1;i++)
            cout<<"L";

        memset(vis,0,sizeof(vis));//第二次寻路
        flag=0;
        vis[0][0]=1;
        dfs(0,0,px,py,path);

        cout<<endl;
    }
    return 0;
}

转载自原文链接, 如需删除请联系管理员。

原文链接：神奇怪兽在哪里 DFS，转载请注明来源！

赞 0