O(∩_∩)O~~第一篇博客上的解题报告

先给出题目链接 Ignatius and the Princess I

以下为题目原文：

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.
范例输入输出就不贴了~

一个迷宫，迷宫包含空白格子(.)，不能走的格子(X)和需要花费一定时间击败怪物(int 0~9)的格子。从(0,0)走到(n-1,m-1)，求耗费时间最少的路径。

很明显这道题是用搜索去解，既然是最短路那就BFS咯，顺便参照一个大神的博客整理一下BFS和DFS的区别：

“当已知最大可能步骤数的时候，DFS可用，当最大可能步骤数未知时，BFS可用。同时也要视确切问题及其数学模型对于两种算法的适应程度决定使用哪一种算法。

对于DFS，问题在于找到解后无法确定是否是目标的最优解，对于求最优解问题的处理比较困难。对于BFS，局限性在于所 有已经处理过的情况均保留在队列中，对于空间占用比较大，以及对各情况的判重有时难度较高。“

总结就是：

DFS：已知最大可能步骤（搜索深度）时适用，有时候对于最优解的处理比较困难。递归实现。

BFS：最大步骤（搜索深度）未知时适用，因为需要用队列储存一部分节点（状态），所以对空间的消耗会比较大。判断状态重复有时候会比较麻烦。队列实现。

虽然一开始就明确了要用BFS，但是自己还是想了很久，因为题目不仅要求输出最短耗时，而且需要输出最短路径，并且不同于一般的BFS其中还有需要花费一定时间通过的格子，不能按常规去BFS，这题的难点主要在1、花费时间才能通过的格子2、输出最短路径

首先，对迷宫预处理，定义一个二维数组存储：

static int maze[][]=new int[102][102];//-1:陷阱 0:空白 1~9:方格内怪兽的hp

然后，自定义一个类以便于队列搜索点：

static class point{
        int x=0,y=0,d=0;
        public point(int a,int b,int c){
            this.x=a;
            this.y=b;
            this.d=c;
        }
}

然后，，，就没有然后了，这样下去是行不通的，没有考虑到有怪物格子可能花费的时间，也没有考虑到记录路径。

最终还是在大神的帮助下，通过如下定义类的方式，一举解决了两个问题：

static class point{
        int x=0,y=0;
        public point(int a,int b){
            this.x=a;
            this.y=b;
        }
    }
    static class pre_point{
        int pre_x,pre_y,time;
        public pre_point(int a,int b,int c){
            this.pre_x=a;  
            this.pre_y=b;  //当前点最优的前驱点的x，y坐标
            this.time=c;   //到达当前点最优的耗时
        }
    }
    static pre_point path[][]=new pre_point[102][102];

这样处理通过一个pre_point类，非常聪明的解决了输出路径的问题，而第一个问题，将path数组的time都初始化为一个足够大的值，然后用BFS去更新（当path[sx][sy].time>path[get.x][get.y].time+maze[sx][sy]+1的时候更新path[sx][sy].time），如果一个点被更新而且不在队中则将该点入队，因为到达一个点的最优路径和时间变化以后该点能到达的点的相应数据也需要被更新.注意前驱点坐标和time都要更新。当队列为空时结束更新。

至于讨论版和其他博客说的优先队列，，，Orz….现在还不懂，以后会了再加上吧。

最后，将path[n-1][m-1]的时间取出，并从该点把前驱点坐标一一取出并压入栈中，一直到点（0,0），最后再pop出来，同时注意判断点上是否有怪，注意细节处理，输出即可。

最后是AC java代码- -有点乱，仅供参考：

package part_BFS;
import java.io.PrintWriter;
import java.util.Scanner;
import java.util.Queue;
import java.util.ArrayDeque;
import java.util.Stack;
public class hdoj1026b {
    static PrintWriter cout = new PrintWriter(System.out, true);
    static Scanner cin = new Scanner(System.in);
    static int n=0, m=0,max=1000000;
    static int dx[]=new int[]{1,-1,0,0},dy[]=new int[]{0,0,1,-1};
    static int maze[][]=new int[102][102];
    static Queue<point>que=new ArrayDeque<point>();
    static Stack<point>sta=new Stack<point>();
    static boolean vivs[][]=new boolean[102][102];
    static pre_point path[][]=new pre_point[102][102];
    static class point{
        int x=0,y=0;
        public point(int a,int b){
            this.x=a;
            this.y=b;
        }
    }
    static class pre_point{
        int pre_x,pre_y,time;
        public pre_point(int a,int b,int c){
            this.pre_x=a;
            this.pre_y=b;
            this.time=c;
        }
    }
    public static void main(String[] args) {
        while(cin.hasNext()){
            n = cin.nextInt();
            m = cin.nextInt();
            for(int i=0;i<n;i++){
                String temp=cin.next();
                for(int j=0;j<m;j++){
                    if(temp.charAt(j)=='X'){
                        maze[i][j]=-1;
                    }
                    else if(temp.charAt(j)=='.'){
                        maze[i][j]=0;
                    }
                    else{
                        maze[i][j]=temp.charAt(j)-'0';
                    }
                }
            }

            for(int i=0;i<102;i++){
                for(int j=0;j<102;j++){
                    vivs[i][j]=false;
                    path[i][j]=new pre_point(0,0,max);
                }
            }
            que.clear();
            bfs();
            print();
        }
    }
    static void bfs(){
        point a=new point(0,0);
        que.add(a);
        vivs[0][0]=true;
        path[0][0].time=0;
        path[0][0].pre_x=-1;
        while(!que.isEmpty()){
            point get=que.poll();
            vivs[get.x][get.y]=false;
            for(int i=0;i<4;i++){
                int sx=get.x+dx[i],sy=get.y+dy[i];
                if(sx>=0&&sy>=0&&sx<n&&sy<m){
                    if(path[sx][sy].time>path[get.x][get.y].time+maze[sx][sy]+1&&maze[sx][sy]!=-1){
                        path[sx][sy].time=path[get.x][get.y].time+maze[sx][sy]+1;
                        path[sx][sy].pre_x=get.x;
                        path[sx][sy].pre_y=get.y;
                        if(!vivs[sx][sy]){
                            vivs[sx][sy]=true;
                            point newp=new point(sx,sy);
                            que.add(newp);
                        }
                    }
                }
            }

        }
    }
    static void print(){
        if(path[n-1][m-1].time!=max){
            int t=path[n-1][m-1].time;
            int kx=n-1,ky=m-1;
            sta.add(new point(n-1,m-1));
            while(path[kx][ky].pre_x>-1){
                point s=new point(path[kx][ky].pre_x,path[kx][ky].pre_y);
                sta.add(s);
                kx=s.x;
                ky=s.y;
            }
            cout.println("It takes "+t+" seconds to reach the target position, let me show you the way.");
            point pre=sta.pop();
            point a=sta.pop();
            int time=1;
            while(!sta.isEmpty()){
                cout.println((time++)+"s:"+"("+pre.x+","+pre.y+")"+"->("+a.x+","+a.y+")");
                while(maze[a.x][a.y]>0){
                    cout.println((time++)+"s:FIGHT AT ("+a.x+","+a.y+")");
                    maze[a.x][a.y]--;
                }
                pre=a;
                a=sta.pop();
            }
            cout.println((time++)+"s:"+"("+pre.x+","+pre.y+")"+"->("+a.x+","+a.y+")");
            while(maze[a.x][a.y]>0){
                cout.println((time++)+"s:FIGHT AT ("+a.x+","+a.y+")");
                maze[a.x][a.y]--;
            }
        }
        else{
            cout.println("God please help our poor hero.");
        }
        cout.println("FINISH");
    }
}