PDSOJ 1759 逃出迷宫

朴灿烈づ我的快乐病毒、 2022-06-17 00:48 97阅读 0赞

## [1759: 逃出迷宫][1759_] ##

时间限制: 1 Sec   内存限制: 128 MB  
提交: 25   解决: 13  
\[ [提交][Link 1]\]\[ [状态][Link 2]\]\[ [讨论版][Link 3]\]

## 题目描述 ##

现在有一个迷宫，'a'代表起点位置，'.'代表可以通行的路，'\#'代表不能通过的墙，'x'代表迷宫的守卫，'r'代表终点位置，  
现在要求你算出起点位置到终点位置的最短时间，其中通过'.'时，消耗1个单位时间，通过'x'消耗两个单位时间。

## 输入 ##

多组测试数据，输入两个整数（X，Y）代表迷宫的长和宽，之后输入迷宫。

## 输出 ##

如果可以到达终点，输出到达终点的最短时间。如果不能到达终点输出"Oh No!"。

## 样例输入 ##

7 8
    #.#####.
    #.a#..r.
    #..#x...
    ..#..#.#
    #...##..
    .#......
    ........

## 样例输出 ##

主要是一个深搜然后用上了优先队列来求最优解

#include<bits/stdc++.h>
    using namespace std;
    char ch[105][105];
    int dir[4][2]={
        {-1,0},{1,0},{0,-1},{0,1}};
    int vis[105][105];
    int n,m;
    struct node
    {
        int x,y;
        int time;
        friend bool operator<(node a,node b)         //定义优先队列的排序方法
        {
            return a.time>b.time;
        }
    }p,q;
    void dfs()
    {
        int flag=0;                  //flag标记是否能出去
        priority_queue<node>Q;      //创建一个优先队列
        p.time=0;
        Q.push(p);
        vis[p.x][p.y]=1;
        while(!Q.empty())
        {
            q=Q.top();          //优先队列取队首元素用.top()而不是.front()!!!!!!!
            Q.pop();
            if(ch[q.x][q.y]=='r')
            {
                printf("%d\n",q.time);
                flag=1;          
                return ;
            }
            for(int i=0;i<4;i++)
            {
                p.x=q.x+dir[i][0];
                p.y=q.y+dir[i][1];
                p.time=q.time+1;
                if(p.x>=1&&p.x<=n&&p.y>=1&&p.y<=m&&ch[p.x][p.y]!='#'&&vis[p.x][p.y]==0)
                {
                    if(ch[p.x][p.y]=='x')
                    {
                        p.time=p.time+1;
                    }
                    vis[p.x][p.y]=1;
                    Q.push(p);
                }
            }
        }
        if(flag==0)
            printf("Oh No!\n");
    }
    int main()
    {
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            getchar();
            memset(vis,0,sizeof(vis));
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=m;j++)
                {
                    scanf("%c",&ch[i][j]);
                    if(ch[i][j]=='a')
                    {
                        p.x=i;
                        p.y=j;
                    }
                }
                getchar();
            }
            dfs();
        }
        return 0;
    }

[1759_]: http://211.69.26.100/problem.php?id=1759
[Link 1]: http://211.69.26.100/submitpage.php?id=1759
[Link 2]: http://211.69.26.100/problemstatus.php?id=1759
[Link 3]: http://211.69.26.100/bbs.php?pid=1759