UVA 816 Abbott's Revenge

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_PRoblem&problem=757

BFS,有点复杂，看着别人的代码调试了半天，争取自己写出来。

import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;import java.util.Vector;public class Main {	static Scanner scan = new Scanner(System.in);	static String dirs = "NESW";	static String turns = "FLR";	static boolean[][][][] has_edge = new boolean[10][10][4][3];	static Node[][][] p = new Node[10][10][4];	static int[][][] d = new int[10][10][4];	static int[] dr = {-1,0,1,0};	static int[] dc = {0,1,0,-1};	static int r1,c1,dir,r2,c2,r0,c0;	/**	 * @param args	 */	public static void main(String[] args) {		// TODO Auto-generated method stub		while(input()){			slove();		}			}		//输入	public static boolean input(){		for(int i=1;i<=9;i++){			for(int j=1;j<=9;j++){				for(int k=0;k<4;k++){					for(int l=0;l<3;l++){						has_edge[i][j][k][l] = false;					}				}			}		}		String name = scan.next();		if("END".equals(name))			return false;		r0 = scan.nextInt();		c0 = scan.nextInt();		char c = scan.next().charAt(0);		r2 = scan.nextInt();		c2 = scan.nextInt();		dir = dir_id(c);		r1 = r0 + dr[dir];		c1 = c0 + dc[dir];				while(true){			int x = scan.nextInt();			if(x==0)				break;			int y = scan.nextInt();			while(true){				String str = scan.next();				if(str.charAt(0)=='*')					break;				int dd = dir_id(str.charAt(0));				for(int i=1;i<str.length();i++){					has_edge[x][y][dd][turn_id(str.charAt(i))] = true;				}			}		}				System.out.println(name);		return true;	}	//将方向转化为数字	public static int dir_id(char c){		return dirs.indexOf(c);	}		//将转向转化为数字	public static int turn_id(char c){		return turns.indexOf(c);	}		//判断坐标是否合法	public static boolean inSide(int x,int y){		return x>0&&x<=9&&y>0&&y<=9;	}		//BFS	public static void slove(){		Queue<Node> q = new LinkedList<>();		for(int i=1;i<=9;i++){			for(int j=1;j<=9;j++){				for(int k=0;k<4;k++){					d[i][j][k] = -1;				}			}		}	//	System.out.println(r2+","+c2+","+dir);		Node u = new Node(r1,c1,dir);		d[u.r][u.c][u.dir] = 0;		q.add(u);		while(!q.isEmpty()){			u = q.poll();			if(u.r==r2&&u.c==c2){				print_ans(u);				return;			}			for(int i=0;i<3;i++){				Node v = walk(u,i);				if(has_edge[u.r][u.c][u.dir][i]&&inSide(v.r,v.c)&&d[v.r][v.c][v.dir]<0){					d[v.r][v.c][v.dir] = d[u.r][u.c][u.dir]+1;					p[v.r][v.c][v.dir] = u;					q.add(v);				}			}		}		System.out.println("  No Solution Possible");	}		//控制下一步的方向	private static Node walk(Node u, int turn) {		int dir = u.dir;		if(turn == 1){//逆时针			dir =(dir+3)%4;		}				if(turn == 2){//顺时针			dir = (dir+1)%4;		}		return new Node(u.r+dr[dir],u.c+dc[dir],dir);	}	//输出答案	private static void print_ans(Node u) {		Vector<Node> nodes = new Vector<>();		for(;;){			nodes.add(u);			if(d[u.r][u.c][u.dir]==0){				break;			}			u = p[u.r][u.c][u.dir];		}		nodes.add(new Node(r0,c0,dir));		int cnt = 0;		for(int i=nodes.size()-1;i>=0;i--){			if(cnt%10==0)				System.out.print(" ");			System.out.printf(" (%d,%d)",nodes.get(i).r,nodes.get(i).c);			if(++cnt%10==0)				System.out.println();		}		if(nodes.size()%10!=0){			System.out.println();		}	}		//每个节点的信息，包含坐标，和从哪个方向来的	static class Node{		int r=0,c=0,dir=0;		public Node(int r,int c,int dir){			this.r = r;			this.c = c;			this.dir = dir;		}	}}