其实就是BFS求最短路，先说明为什么BFS可以求最短路。因为BFS是广度搜索，是一层一层的，最先到达约定条件的那一层一定是最短的。
本题复杂在方向判断上，首先需要用数组has_edge[r][c][dir][trun]来记录从方向dir到达r,c点，转向turn是否可行。
然后用d[r][c][dir]来记录从方向dir到r,c的长度，p[r][c][dir]记录从方向dir到r,c的父节点。
关于转向，可以在每个点都用一个for(int i=0;i<3;i++),当i==0表示直线,i==1表示左转，i==2表示右转。对每个方向都判断一下，因为我们用has_edge数组记录在点r,c的某个转向是否可行。
import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.Vector; public class Main { static String dirs = "NESW"; static String turns = "FLR"; static int[] dr = {-1,0,1,0}; static int[] dc = {0,1,0,-1}; static int r0,r1,r2,c0,c1,c2,dir; static int[][][][] has_edge = new int[10][10][4][3]; static int[][][] d = new int[10][10][4]; static Node[][][] p = new Node[10][10][4]; public static void main(String[] args) { Scanner scan = new Scanner(System.in); while(true){ String name = scan.next(); if("END".equals(name))break; 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] = 0; } } } } r0 = scan.nextInt(); c0 = scan.nextInt(); dir = dir_id(scan.next().charAt(0)); r2 = scan.nextInt(); c2 = scan.nextInt(); r1 = r0+dr[dir]; c1 = c0+dc[dir]; while(true){ int r = scan.nextInt(); if(r==0)break; int c = scan.nextInt(); while(true){ String str = scan.next(); char dd = str.charAt(0); if(dd=='*')break; for(int i=1;i<str.length();i++){ has_edge[r][c][dir_id(dd)][turn_id(str.charAt(i))]=1; } } } System.out.println(name); solve(); } } public static void solve(){ 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] = 0; p[i][j][k] = null; } } } Queue<Node> q = new LinkedList<>(); 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; }else{ for(int i=0;i<3;i++){ Node v = walk(u,i); if(has_edge[u.r][u.c][u.dir][i]==1&&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"); } public static void print_ans(Node u){ Vector<Node> v = new Vector<>(); for(;;){ v.add(u); if(d[u.r][u.c][u.dir]==0)break; u = p[u.r][u.c][u.dir]; } v.add(new Node(r0,c0,dir)); int cnt = 0; for(int i=v.size()-1;i>=0;i--){ if(cnt==0)System.out.print(" "); System.out.printf(" (%d,%d)",v.get(i).r,v.get(i).c); if(++cnt==0)System.out.println(); } if(v.size()!=0){ System.out.println(); } } public static boolean inside(int r,int c){ return r>=1&&r<=9&&c>=1&&c<=9; } public 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); } public static int dir_id(char c){ return dirs.indexOf(c); } public static int turn_id(char c){ return turns.indexOf(c); } static class Node{ int r,c,dir; public Node(int r,int c,int dir){ this.r = r; this.c = c; this.dir = dir; } } }
