`

hdu 1026 Ignatius and the Princess I

    博客分类:
  • bfs
阅读更多

Ignatius and the Princess I

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4313    Accepted Submission(s): 1348
Special Judge

Problem Description
The Princess has been abducted by the BEelzebub feng5166, our hero Ignatius has to rescue our pretty Princess. Now he gets into feng5166's castle. The castle is a large labyrinth. To make the problem simply, we assume the labyrinth is a N*M two-dimensional array which left-top corner is (0,0) and right-bottom corner is (N-1,M-1). Ignatius enters at (0,0), and the door to feng5166's room is at (N-1,M-1), that is our target. There are some monsters in the castle, if Ignatius meet them, he has to kill them. Here is some rules:

1.Ignatius can only move in four directions(up, down, left, right), one step per second. A step is defined as follow: if current position is (x,y), after a step, Ignatius can only stand on (x-1,y), (x+1,y), (x,y-1) or (x,y+1).
2.The array is marked with some characters and numbers. We define them like this:
. : The place where Ignatius can walk on.
X : The place is a trap, Ignatius should not walk on it.
n : Here is a monster with n HP(1<=n<=9), if Ignatius walk on it, it takes him n seconds to kill the monster.

Your task is to give out the path which costs minimum seconds for Ignatius to reach target position. You may assume that the start position and the target position will never be a trap, and there will never be a monster at the start position.

 

Input
The input contains several test cases. Each test case starts with a line contains two numbers N and M(2<=N<=100,2<=M<=100) which indicate the size of the labyrinth. Then a N*M two-dimensional array follows, which describe the whole labyrinth. The input is terminated by the end of file. More details in the Sample Input.

 

Output
For each test case, you should output "God please help our poor hero." if Ignatius can't reach the target position, or you should output "It takes n seconds to reach the target position, let me show you the way."(n is the minimum seconds), and tell our hero the whole path. Output a line contains "FINISH" after each test case. If there are more than one path, any one is OK in this problem. More details in the Sample Output.

 

Sample Input
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.

 

Sample Output
It takes 13 seconds to reach the target position, let me show you the way. 1s:(0,0)->(1,0) 2s:(1,0)->(1,1) 3s:(1,1)->(2,1) 4s:(2,1)->(2,2) 5s:(2,2)->(2,3) 6s:(2,3)->(1,3) 7s:(1,3)->(1,4) 8s:FIGHT AT (1,4) 9s:FIGHT AT (1,4) 10s:(1,4)->(1,5) 11s:(1,5)->(2,5) 12s:(2,5)->(3,5) 13s:(3,5)->(4,5) FINISH It takes 14 seconds to reach the target position, let me show you the way. 1s:(0,0)->(1,0) 2s:(1,0)->(1,1) 3s:(1,1)->(2,1) 4s:(2,1)->(2,2) 5s:(2,2)->(2,3) 6s:(2,3)->(1,3) 7s:(1,3)->(1,4) 8s:FIGHT AT (1,4) 9s:FIGHT AT (1,4) 10s:(1,4)->(1,5) 11s:(1,5)->(2,5) 12s:(2,5)->(3,5) 13s:(3,5)->(4,5) 14s:FIGHT AT (4,5) FINISH God please help our poor hero. FINISH
      该题的难点就是:如何记录以最短时间到达目标的路径,并输出它每一秒的状态。解决这个问题,要用到优先队列和栈!!!
要注意一下几点:
1.因为他要最短时间到达,所以要用到优先队列,时间短的先作处理;
2.因为要记录到达目标的路径,所以要开个map[][]2维数组来保存他之前来的那个坐标;
3.最后,你要从目标倒推到起点,并从起点的坐标开始输出到目标的路径,这个就要用的栈了。
我的代码(有注释):
#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <queue>
#include <stack>
using namespace std;

int xx[4] = {1, -1, 0, 0};
int yy[4] = {0, 0, -1, 1};

int nn, mm;
char a[105][105];
int map[105][105];
bool flag;

struct node
{
    friend bool operator < (node a, node b)
    {
        return a.time > b.time; //时间短的优先
    }
    int x, y, time;
    int px, py;         //px,py是保存上一点的记录
}n, m, ch[105][105];    //ch数组代表每一个坐标

int main()
{
    int i, j, ant;
    while(scanf("%d %d", &nn, &mm) != EOF)
    {
        for(i = 0; i < nn; i++)
        {
            getchar();
            for(j = 0; j < mm; j++)
            {
                scanf("%c", &a[i][j]);
                map[i][j] = 1000000;
            }
        }
        flag = false;
        n.px = n.py = -1;
        n.x = n.y = n.time = 0;
        priority_queue<node> Q; //建立优先队列
        Q.push(n);
        while(!Q.empty())
        {
            m = Q.top();
            Q.pop();
            if(m.x == nn-1 && m.y == mm-1)  //找到目标
            {
                flag = true;
                break;
            }
            for(i = 0; i < 4; i++)
            {
                n.x = m.x + xx[i];
                n.y = m.y + yy[i];
                if(n.x>=0 && n.x<nn && m.y>=0 && m.y<mm && a[n.x][n.y] != 'X')
                {
                    if(a[n.x][n.y] == '.') n.time = m.time + 1;
                    else n.time = m.time + (a[n.x][n.y] - '0') + 1; //打怪消耗时间
                    if(n.time < map[n.x][n.y])
                    {
                        //记录来该坐标的点(x,y)
                        ch[n.x][n.y].px = m.x;
                        ch[n.x][n.y].py = m.y;
                        map[n.x][n.y] = n.time; //更新该点时间
                        Q.push(n);
                    }
                }
            }
        }

        if(flag)    //找到目标后
        {
            printf("It takes %d seconds to reach the target position, let me show you the way.\n", m.time);
            stack<node> st; //用到stack盏
            n.x = nn-1;
            n.y = mm-1;
            st.push(n);
            while(1)
            {
                m = st.top();
                if(m.x==0 && m.y==0)
                    break;
                n.x = ch[m.x][m.y].px;
                n.y = ch[m.x][m.y].py;
                st.push(n);     //push每一个坐标之前的点
            }
            ant = 1;
            st.pop();
            while(!st.empty())
            {
                m = st.top();
                st.pop();
                if(a[m.x][m.y] == '.')  //该点是普通的点
                {
                    printf("%ds:(%d,%d)->(%d,%d)\n", ant++,
                       ch[m.x][m.y].px, ch[m.x][m.y].py, m.x, m.y);
                }
                else    //否则是打怪的点
                {
                    printf("%ds:(%d,%d)->(%d,%d)\n", ant++,
                       ch[m.x][m.y].px, ch[m.x][m.y].py, m.x, m.y);
                    for(i = 0; i < a[m.x][m.y]-'0'; i++)
                    {
                        printf("%ds:FIGHT AT (%d,%d)\n", ant++, m.x, m.y);
                    }
                }
            }
            printf("FINISH\n");
        }
        else    //去不到目标
        {
            printf("God please help our poor hero.\n");
            printf("FINISH\n");
        }
    }

    return 0;
}
 
0
5
分享到:
评论

相关推荐

    HDU图论题目分类

    * 题目1026:Ignatius and the Princess I,涉及到完全搜索的概念。 2. 图的遍历:深度优先搜索(DFS)、广度优先搜索(BFS)等。 * 题目1043:Eight,涉及到多种解决方法。 * 题目1044:Collect More Jewels,涉及...

    hdu.rar_hdu

    HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...

    HDU 1022 Train Problem I 附详细思路

    HDU 1022 Train Problem I 附详细思路

    HDU_2010.rar_hdu 2010_hdu 20_hdu acm20

    【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...

    HDU题目java实现

    【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...

    ACM HDU题目分类

    ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...

    HDU1019(2028)解题报告

    nm where m is the number of integers in the set and n1 ... nm are the integers. All integers will be positive and lie within the range of a 32-bit integer. Output For each problem instance, output a ...

    hdu1250高精度加法

    ### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...

    HDU DP动态规划

    【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...

    HDU1059的代码

    HDU1059的代码

    code_hdu.rar_ACM_The First_hdu_test case example

    You are given the value of m and (f(n,m)?n)⊕n, where ``⊕’’ denotes the bitwise XOR operation. Please write a program to find the smallest positive integer n that (f(n,m)?n)⊕n=k, or determine it ...

    hdu1001解题报告

    hdu1001解题报告

    hdu 1574 passed sorce

    hdu 1574 passed sorce

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

    hdu2101解决方案

    hdu2101AC代码

    hdu动态规划算法集锦

    - 状态转移方程:$f[j] = \max\{f[j], f[j - q[i].money] + q[i].v\}$,其中$q[i].money$是第$i$个地点的价值,$q[i].v$是第$i$个地点的花费。 - 初始条件:$f[0] = 1$(不抢劫任何地方的情况)。 #### 3A:100A:...

    ACM HDU

    【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...

    杭电ACMhdu1163

    【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...

    hdu 5007 Post Robot

    hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。

    解题代码 hdu1241

    根据给定的文件信息,我们可以得知这是一段用于解决HDU(Hdu Online Judge)编号为1241的问题的代码。该代码主要采用了深度优先搜索(DFS)算法来解决问题。 #### 二、DFS(Depth First Search)算法原理 **定义:...

Global site tag (gtag.js) - Google Analytics