basic.java

Ulm大学2005-2006年竞赛题

import java.io.*;
import java.util.*;

public class basic {
	public static void main(String [] args) throws Exception {
		int [] dx = new int[4];
		int [] dy = new int[4];
		String dirname = "NESW";
		dx[0] = -1;
		dy[0] = 0;
		dx[1] = 0;
		dy[1] = 1;
		dx[2] = 1;
		dy[2] = 0;
		dx[3] = 0;
		dy[3] = -1;
		Scanner in = new Scanner(new File("basic.in"));
		int sx,sy,ex,ey;
		while(true) {
			sy = in.nextInt();
			sx = in.nextInt();
			if (sx == 0 && sy == 0)
				break;
			ey = in.nextInt();
			ex = in.nextInt();
			// represent the grid as 6 x 6 squares separated by borders
			// -> 13 x 13 grid, borders at even rows/columns (0 to 12)
			boolean [][]  visit = new boolean[13][13]; // initialized to false
			int [][] prev = new int[13][13];
			// disallow leaving the grid
			for (int i=0; i<13; i++)
				visit[i][0] = visit[0][i] = visit[i][12] = visit[12][i] = true;
			// mark positions of walls
			for (int i=0; i<3; i++) {
				int x1,y1,x2,y2;
				x1 = in.nextInt();
				y1 = in.nextInt();
				x2 = in.nextInt();
				y2 = in.nextInt();
				x1 *= 2;
				y1 *= 2;
				x2 *= 2;
				y2 *= 2;
				if (x1 == x2)
					while(y1 <= y2) {
						visit[y1][x1] = true;
						++y1;
					}
				else
					while(x1 <= x2) {
						visit[y1][x1] = true;
						++x1;
					}
			}
			// do a breadth first search to find shortest path
			int [] qx = new int[11*11+1];
			int [] qy = new int[11*11+1];
			sx = sx*2-1;
			sy = sy*2-1;
			ex = ex*2-1;
			ey = ey*2-1;
			qx[0] = sx;
			qy[0] = sy;
			visit[sx][sy] = true;
			int l = 1;
			for (int i=0; i<l && !visit[ex][ey]; i++) {
				for (int d=0; d<4; d++) {
					qx[l] = qx[i]+dx[d];
					qy[l] = qy[i]+dy[d];
					if (!visit[qx[l]][qy[l]]) {
						visit[qx[l]][qy[l]] = true;
						prev[qx[l]][qy[l]] = d;
						++l;
					}
				}
			}
			StringBuffer path = new StringBuffer();
			do {
				int cur_dir = prev[ex][ey];
				if (ex % 2 != 0 && ey % 2 != 0)
					path.append(dirname.charAt(cur_dir));
				ex -= dx[cur_dir];
				ey -= dy[cur_dir];
			}while(sx != ex || sy != ey);
			System.out.println(path.reverse());
		}
	}
}