uva816

116 阅读 0 评论 77 点赞

我是靠谱客的博主高大狗，最近开发中收集的这篇文章主要介绍uva816，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

思路：主要是方向判断

package test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;


public class Test{	
	static Scanner sc = new Scanner(System.in);
	static String line;
	
	public static class Node{
		int r,c,dir;
		
		public Node(int r, int c, int dir) {
			super();
			this.r = r;
			this.c = c;
			this.dir = dir;
		}				
		
		@Override
		public boolean equals(Object obj) {
			Node n = (Node) obj;
			return (r==n.r&&c==n.c);		
		}			
		
		@Override
		public String toString() {			
			return "("+r+","+c+")";
		}
	}
	
	static char[] dirs = {'N','E','S','W'};
	static char[] turns = {'F','L','R'};
	
	static int[] dr = {-1,0,1,0};//与dc构成是个方向上的坐标变动
	static int[] dc = {-1,0,1,0};
	
	static int n = 9;//迷宫行列数
	static int[][][][] has_edge = new int[n][n][4][3];//记录某点，四个方向进入，某个方向对应的三种转向是否存在
	static int[][][] d = new int[n][n][4];//表示从初状态到r,c,dir的最短路径的长度
	
	static Node[][][] p = new Node[n][n][4];//记录父路径
	
	static int r1,c1,dir;//初始状态
	static int r2,c2;//目标状态
	/**
	 * 把方向字符转换成数字
	 * @param c
	 * @return
	 */
	static int dir_id(char c){
		return Arrays.binarySearch(dirs, c);		 
	}
	
	/**
	 * 把转向字符转换成数字
	 * @param c
	 * @return
	 */
	static int turn_id(char c){
		return Arrays.binarySearch(turns, c);		 
	}
	
	/**
	 * 改变转向
	 * @param u
	 * @param turn
	 * @return
	 */
	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,u.c,dir);
	}
	
	static void solve(){			
		Queue<Node> queue = new LinkedList <Node>();//栈
		Node n = new Node(r1,c1,dir);//起始点		
		queue.add(n);
		
		while(!queue.isEmpty()){
			Node u = queue.poll();
			if(u.r==r2&&u.c==r2){
				print_ans(u);
				return;
			}
			for(int i=0;i<3;i++){
				Node v = walk(u,i);//转身
				if(has_edge[v.r][v.c][v.dir][i]==1 && d[v.r][v.c][v.dir]<1 
						&& inside(v.r,v.c)){//如果存在该方向，并且没有走过，并且
					d[v.r][v.c][v.dir] = d[u.r][u.c][u.dir] + 1;//路径加一
					p[v.r][v.c][v.dir] = u;//记录下父节点
					queue.add(v);
				}
			}
		}	
	}
	
	static boolean inside(int x,int y){
	  if(x>=1&&x<=n&&y>=1&&y<=n) return true;
	  return false;
	}
	
	private static void print_ans(Node u) {
		ArrayList<Node> nodes = new ArrayList<Node>();
		for(;;){
			nodes.add(u);
			if(d[u.r][u.c][u.dir]==0) break;
			u = p[u.r][u.c][u.dir];
		}
		
		System.out.println(nodes);
	}

	public static void main(String[] args) {
		solve();
		System.out.println(Arrays.deepToString(p));
	}
}