Ignatius and the Princess I

   

    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, 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
   

题意：一个N*M的图，一秒内可上下左右选个方向走一步，一进去，若有数字，就要花数字大小的时间停留在那个格子，输出从起点(0, 0)到终点(N-1, M-1)每一秒的路径。

思路： 优先队列+BFS（广度优先搜索）

import java.io.*;
import java.util.*;
public class Main {
	int n,m;
	char ch[][];
	boolean boo[][];
	int fx[]={1,-1,0,0};
	int fy[]={0,0,-1,1};
	Queue<Node> que=new PriorityQueue<Node>();//优先队列
	public static void main(String[] args) {
		new Main().work();
	}
	void work(){
		Scanner sc=new Scanner(new BufferedInputStream(System.in));
		while(sc.hasNext()){
			que.clear();
			n=sc.nextInt();
			m=sc.nextInt();
			ch=new char[n][m];
			boo=new boolean[n][m];
			for(int i=0;i<n;i++){
				String s=sc.next();
				ch[i]=s.toCharArray();
				Arrays.fill(boo[i],false);
			}
			Node node=new Node();
			node.x=0;
			node.y=0;
			node.t=0;
			String s1="("+node.x+","+node.y+")";
			node.s=s1+" ";
			boo[node.x][node.y]=true;;
			que.add(node);
			BFS();
		}
	}
	void BFS(){
		while(!que.isEmpty()){
			Node node=que.poll();
			if((node.x==n-1)&&(node.y==m-1)){
				out(node.s,node.t);
				return;
			}
			for(int i=0;i<4;i++){
				int px=node.x+fx[i];
				int py=node.y+fy[i];
				if(check(px,py)&&!boo[px][py]){
					boo[px][py]=true;
					Node td=node.getNode();
					td.x=px;
					td.y=py;
					String s1="("+td.x+","+td.y+")";
					td.s+=s1+" ";
					if(ch[px][py]=='.'){
						td.t=td.t+1;
					}
					else{
						td.t=td.t+(ch[px][py]-'0');
						td.t=td.t+1;
						for(int j=0;j<ch[px][py]-'0';j++){
							td.s+=s1+" ";
						}
					}
					que.add(td);
				}
			}
		}
		System.out.println("God please help our poor hero.");
		System.out.println("FINISH");
	}
	//输出
	void out(String s,int time){
		System.out.println("It takes "+time+" seconds to reach the target position, let me show you the way.");
		String str[]=s.split(" ");
		for(int i=1;i<str.length;i++){
			if(str[i].length()!=0){
				System.out.print(i+"s:");
				if(str[i-1].equals(str[i])){
					System.out.println("FIGHT AT "+str[i]);
				}
				else{
					System.out.println(str[i-1]+"->"+str[i]);
				}
			}
		}
		System.out.println("FINISH");
	}
	boolean check(int px,int py){
		if(px<0||px>n-1||py<0||py>m-1||ch[px][py]=='X')
			return false;
		return true;
	}
	class Node implements Comparable<Node>{
		int x;
		int y;
		int t;
		String s;
		public int getT() {
			return t;
		}
		public void setT(int t) {
			this.t = t;
		}
		Node getNode(){
			Node node=new Node();
			node.t=t;
			node.s=s;
			return node;
		}
		public int compareTo(Node o) {//按升序排序
			return this.t>o.t?1:-1;
		}
	}
}