拯救公主 (Ver. II)-布布扣-bubuko.com

题目描述

公主被BEelzebub feng5166绑架，我们的英雄Ignatius必须拯救我们漂亮的公主。现在他进入了feng5166的城堡。城堡是一个大型的迷宫。为了简单地解决这个问题，我们假设迷宫是一个N * M的二维数组，左上角是（0,0），右下角是（N-1，M-1）。Ignatius进入（0,0），feng5166房间的门是（N-1，M-1），这是我们的目标。城堡里有一些怪物，如果Ignatius遇见他们，他必须杀死他们。这是一些规则：

1.Ignatius只能向四个方向（上，下，左，右）移动，一步一秒。步骤定义如下：如果当前位置为（x，y），则在步骤之后，Ignatius只能站在（x-1，y），（x + 1，y），（x，y-1）或（X，Y + 1）。
2.数组标有一些字符和数字，定义如下
.：Ignatius可以走路的地方。

X：这个地方是一个陷阱，Ignatius不能走在上面。

n：这是一个拥有n HP（1 <= n <= 9）的怪物，如果Ignatius走上它，他需要n秒才能杀死怪物。

你的任务是给出Ignatius达到目标位置所需的最小秒数。你可以假设起始位置和目标位置永远不会成为陷阱，并且在起始位置永远不会有怪物。

输入

测试数据有多组
每个测试样例以包含两个数字N和M（2 <= N <= 100,2 <= M <= 100）的行开始，这表示迷宫的大小。
然后是N * M二维矩阵，描述整个迷宫。
输入格式见样例输入

输出

对于每个测试样例
如果Ignatius无法到达目标位置，你应该输出“God please help our poor hero.”，或者你应该输出“It takes n seconds to reach the target position.”（n是最小秒数）

样例输入

5 6 .XX.1. ..X.2. 2...X. ...XX. XXXXX. 5 6 .XX.1. ..X.2. 2...X. ...XX. XXXXX1 5 6 .XX... ..XX1. 2...X. ...XX. XXXXX.

样例输出

It takes 13 seconds to reach the target position. It takes 14 seconds to reach the target position. God please help our poor hero.

提示

请使用scanf、printf进行输入输出

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
 
#define INF 0x7f
int array[INF][INF];
int visit[INF][INF];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int N,M;
 
class node
{
public:
    int x,y,sec;
    node()
    {
        x=y=-1;
        sec=0;
    }
    node(int x1,int y1,int sec1)
    {
        x=x1;
        y=y1;
        sec=sec1;
    }
    friend bool operator >(const node &a,const node &b)
    {
        if(a.sec>b.sec)
            return true;
        else
            return false;
    }
};
 
int BFS()
{//向右y正，向下x正
    priority_queue< node,vector<node>,greater<node> >Q;
    node start(0,0,0);
    Q.push(start);
    visit[0][0]=1;
    int tag=0;
    while(!Q.empty())
    {
        if(Q.top().x==N-1&&Q.top().y==M-1)
        {
            tag=1;
            break;
        }
        for(int i=0;i<4;i++)
        {
            int nx=Q.top().x;
            int ny=Q.top().y;
            nx+=dx[i];
            ny+=dy[i];
            if(nx>=0&&nx<=N-1&&ny>=0&&ny<=M-1)
            {
                if(array[nx][ny]>0&&visit[nx][ny]==0)
                {
                    visit[nx][ny]=1;
                    node p(nx,ny,Q.top().sec+array[nx][ny]);
                    Q.push(p);
                }
            }
        }
        Q.pop();
    }
    if(tag==1)
        return Q.top().sec;
    else
        return 0;
}
 
int main()
{
    while(cin>>N>>M)
    {
        memset(array,0,sizeof(array));
        memset(visit,0,sizeof(visit));
        string str;
        for(int i=0;i<N;i++)
        {
            cin>>str;
            for(int j=0;j<M;j++)
            {
                if(str[j]==‘.‘)
                    array[i][j]=1;
                else if(str[j]==‘X‘)
                    array[i][j]=0;
                else
                    array[i][j]=str[j]-‘0‘+1;
            }
        }
        int result=BFS();
        if(result==0)
            cout<<"God please help our poor hero."<<endl;
        else
            cout<<"It takes "<<result<<" seconds to reach the target position."<<endl;
    }
    return 0;
}

拯救公主 (Ver. II)

原文：https://www.cnblogs.com/SZU-DS-wys/p/12182980.html