hdu 1026 Ignatius and the Princess I

Ignatius and the Princess I
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 10006    Accepted Submission(s): 3004
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

Author
Ignatius.L
 

題意：

給你一個 N*M 的圖, 要你從第一個點走到最後一個點【從左上角走到右下角】
只可以按照上下左右四個方向走

. : 代表可以走
 
X :  表示是牆，不可以走

n :  代表這裡有一個怪獸，打敗怪獸用時 n

每走一步耗時 1 .

如果能到達，則輸出最小時間和每一步的走法
不能到達輸出。。。
具體輸出看樣例。

注意：保證起點沒有怪獸，終點不是牆。【也就是說終點可能有怪獸】

 Ignatius and the Princess I
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 10006    Accepted Submission(s): 3004
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

Author
Ignatius.L
 

題意：

給你一個 N*M 的圖, 要你從第一個點走到最後一個點【從左上角走到右下角】
只可以按照上下左右四個方向走

. : 代表可以走
 
X :  表示是牆，不可以走

n :  代表這裡有一個怪獸，打敗怪獸用時 n

每走一步耗時 1 .

如果能到達，則輸出最小時間和每一步的走法
不能到達輸出。。。
具體輸出看樣例。

注意：保證起點沒有怪獸，終點不是牆。【也就是說終點可能有怪獸】

算法：優先隊列+BFS 【本質Dijkstra】

思路：

很裸的最短路了，但是不熟悉優先隊列，用自己的笨方法錯了很久。

正解思路：

由於是用的優先隊列+BFS 為了方便輸出路徑,所以從終點開始搜索。
從起點開始也可以，只是不方便，要麼遞歸輸出路徑點擊打開鏈接
要麼定義一個數組來維護，使得本來就很復雜了的簡單題目越發變得復雜起來。

定義一個優先隊列，包含了位置和當前位置到達終點的最短時間。
優先隊列保證時間短的先出隊。。。

//定義優先隊列：對於入隊了的點,先出隊的是時間少的,那麼第一個到達終點的就是結果
struct Node{
    int x,y; //當前到達的點
    int time; //耗費的時間

    bool operator < (const Node &b) const{
        return b.time < time;
    }
};

關於優先隊列的重載一直不是很清楚。。。

下面我是這麼理解的，每次新加入一個點 b ,不管他們的 x 和 y 也就是默認關於 x 和 y 按照普通的隊列定義，先進先出
 
然後優先考慮 time ，b.time 與原來的隊列中的每一個 time 比較【從隊首往隊伍遍歷】如果一旦遇到了 b.time < time
那麼就把 " b 插入到當前遍歷到的位置". 有待路過的大神詳細指教下。
 
由於優先隊列保證了按照時間少的先出隊，那麼第一個遍歷到起點的一定是所求的最短路了。
後面可能會有其它的路，但是不會比這條路更優。【special judge】
 
下面我們考慮輸出問題：定義一個先驅結構體記錄每一個點的前一個點的位置就好了。
注意：由於搜索的時候為了方便輸出路徑是從終點往起點搜索的，那麼先驅中記錄的點其實是實際走的過程中的下一個點。
 
此題參考博客：點擊打開鏈接
 
 
 
我的開始錯誤思路分析：
 
開始沒有想到用優先隊列搜索，由於前面做過 BFS 倒水問題POJ 3414 Pots【bfs模擬倒水問題】 也是要模擬輸出路徑
就感覺很像，其實錯了。。。然後按照這題的思路寫。
也考慮了會有多條路到達，但是想到點很少才 100*100 就准備直接暴力搜索完所有的點。
開始想的是，一旦到達終點就和原來的比較看能否更優【我以為那個方法會多次到達終點】
其實我入隊的時候標記了，出隊卻沒有標記，所以最多只可能到達一次終點，根本不可能多次到達終點，更新最小時間。
但是樣例出來了，自己怎麼想也想不出錯誤我的錯誤思路代碼
 
後來請教了下南城邊，他給我指出了上面提到的問題，更本不可能更新最小時間。因為按照上面的寫法，終點只可能入隊和出隊一次。
然後我又准備用最短路的思想模擬，但是還是准備在上面的基礎上改一下，於是每一個點出隊我也標記了下，這樣保證了終點可以多次遍歷到
但是這樣一來就無法解決跳出 BFS 問題，於是我想到每一個點最多被上下左右的點走一次，那麼是不是標記每一個點最多入隊四次就可以了呢？
樣例同樣出來了，結果還是 WA 。。。
想了下：可能是我雖然標記了入隊四次，但是可能這四次都是由同一個點到達的，那麼也和標記一次沒有分別了，還是無法解決上面的更新最短時間問題。
 
所以：最終還是只能按照最短路的思想遍歷。
 
很裸的題目了，本來只是打算練下手，結果還是做了很久。菜鳥要努力 Fighting ！！！Come on
 
code：

#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;

const int maxn = 110;
const int INF = maxn*maxn*10;

int map[maxn][maxn]; //記錄圖
int vis[maxn][maxn]; //標記入隊
char str[maxn];
int n,m;

int dir[4][2] = {0,1, 0,-1, -1,0, 1,0};

//定義優先隊列：對於入隊了的點,先出隊的是時間少的,那麼第一個到達終點的就是結果
struct Node{
    int x,y; //當前到達的點
    int time; //耗費的時間

    bool operator < (const Node &b) const{
        return b.time < time;
    }
};

//每一個點的前驅, 由於是逆向搜索的, 所以記錄的其實是當前點的下一個點了
struct Pre{
    int px, py;
}pre[maxn][maxn];

void bfs()
{
    Node now, next;
    priority_queue<Node> q;
    while(!q.empty()) q.pop();

    now.x = n; now.y = m; //從終點走向起點
    now.time = map[n][m]; //注意：終點也可能會有怪獸
    pre[n][m].px = -1; //輸出邊界
    q.push(now);

    memset(vis, 0, sizeof(vis)); //為方便快速輸出路徑, 從終點往起點找
    vis[n][m] = 1; //標記終點入隊

    while(!q.empty())
    {
        now = q.top(); q.pop();

        if(now.x == 1 && now.y == 1) //一旦到達起點
        {
            printf("It takes %d seconds to reach the target position, let me show you the way.\n", now.time);
            int time = 1;
            int x = now.x, y = now.y; //當前的位置
            int nx = pre[x][y].px, ny = pre[x][y].py; //下一個位置
            while(pre[x][y].px != -1) //不停的找前驅
            {
                printf("%ds:(%d,%d)->(%d,%d)\n", time++, x-1, y-1, nx-1, ny-1);
                while(map[nx][ny]--) //如果有怪獸
                {
                    printf("%ds:FIGHT AT (%d,%d)\n", time++, nx-1, ny-1);
                }
                x = nx; y = ny; //繼續查找下一個點
                nx = pre[x][y].px, ny = pre[x][y].py;
            }
            printf("FINISH\n");
            return; //結束
        }

        for(int i = 0; i < 4; i++)
        {
            next.x = now.x+dir[i][0];
            next.y = now.y+dir[i][1];

            if(map[next.x][next.y] >= 0 && !vis[next.x][next.y]) //當前點可以走,並且沒有入隊過
            {
                vis[next.x][next.y] = 1; //標記入隊

                next.time = now.time + 1 + map[next.x][next.y];
                pre[next.x][next.y].px = now.x; //前驅記錄
                pre[next.x][next.y].py = now.y;

                q.push(next);
            }
        }
    }

    printf("God please help our poor hero.\n"); //不能到達
    printf("FINISH\n");
    return;
}

int main()
{
    while(scanf("%d%d", &n,&m) != EOF)
    {
        gets(str);
        for(int i = 0; i <= n+1; i++) //周圍加邊
            for(int j = 0; j <= m+1; j++)
                map[i][j] = -1;

        char c;
        for(int i = 1; i <= n; i++) //輸出的時候注意 -1 處理下
        {
            for(int j = 1; j <= m; j++)
            {
                scanf("%c", &c);
                if(c != 'X')
                {
                    if(c == '.') map[i][j] = 0;
                    else map[i][j] = c-'0';
                }
            }
            gets(str);
        }

        bfs();
    }
    return 0;
}