construct.java

Ulm大学2005-2006年竞赛题

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

public class construct {
	int [][] onPath;
	int [] dx;
	int [] dy;
	int [] wx;
	int [] wy;
	int [] wx2;
	int [] wy2;
	int [][] dist;
	int [] qx;
	int [] qy;
	construct() {
		onPath = new int[6][6];
		dx = new int[4];
		dy = new int[4];
		wx = new int[3];
		wy = new int[3];
		wx2 = new int[3];
		wy2 = new int[3];
		dist = new int[6][6];
		qx = new int[6*6+1];
		qy = new int[6*6+1];
		dx[0] = -1;
		dy[0] = 0;
		dx[1] = 0;
		dy[1] = 1;
		dx[2] = 1;
		dy[2] = 0;
		dx[3] = 0;
		dy[3] = -1;
	}
	// check if wall (wx[a],wy[a])-(wx2[a],wy2[a]) intersects with wall (wx[b],ey[b])-(wx2[b],wy2[b])
	boolean intersect(int a, int b) {
		boolean a_vertical = (wy[a] == wy2[a]);
		boolean b_vertical = (wy[b] == wy2[b]);
		if (a_vertical == b_vertical) {
			if (a_vertical)
				return wy[a] == wy[b] && Math.max(wx[a],wx[b])<Math.min(wx2[a],wx2[b]);
			else
				return wx[a] == wx[b] && Math.max(wy[a],wy[b])<Math.min(wy2[a],wy2[b]);
		}
		if (b_vertical) {
			int temp = a;
			a = b;
			b = temp;
		}
		return wx[a] < wx[b] && wx[b] < wx2[a]
			&& wy[b] < wy[a] && wy[a] < wy2[b];
	}
	// check if the wall (wx[act],wy[act]) - (wx2[act],wy2[act]) does not intersect the path
	boolean isvalid(int act) {
		if (wx[act] == wx2[act]) {
			if (wx[act] > 0 && wx[act] < 6)
				for (int i=wy[act]; i<wy2[act]; i++)
					if (Math.abs(onPath[wx[act]][i]-onPath[wx[act]-1][i]) == 1)
						return false;
			return true;
		}
		if (wy[act] > 0 && wy[act] < 6)
			for (int i=wx[act]; i<wx2[act]; i++)
				if (Math.abs(onPath[i][wy[act]]-onPath[i][wy[act]-1]) == 1)
					return false;
		return true;
	}
	// try all valid combinations of walls (36^3)
	boolean backtrack(int act, int [] l, int len, int sx, int sy, int ex, int ey) {
		if (act == 3) {
			// find shortest path from (sx,sy) to (ex,ey)
			for (int i=0; i<6; i++)
				for (int j=0; j<6; j++)
					dist[i][j] = 1000;
			dist[sx][sy] = 0;
			qx[0] = sx;
			qy[0] = sy;
			int t = 1;
			for (int i=0; i<t && dist[ex][ey] == 1000; i++) {
				int dirs_allowed = 15;
				for (int j=0; j<3; j++) {
					if (wx[j] == wx2[j] && wy[j] <= qy[i] && qy[i] < wy2[j]) {
						if (wx[j] == qx[i])
							dirs_allowed &= (~1);
						else if (wx[j] == qx[i]+1)
							dirs_allowed &= (~4);
					}
					if (wy[j] == wy2[j] && wx[j] <= qx[i] && qx[i] < wx2[j]) {
						if (wy[j] == qy[i])
							dirs_allowed &= (~8);
						else if (wy[j] == qy[i]+1)
							dirs_allowed &= (~2);
					}
				}
				for (int d=0; d<4; d++) {
					if ((dirs_allowed & (1<<d)) == 0)
						continue;
					qx[t] = qx[i]+dx[d];
					qy[t] = qy[i]+dy[d];
					if (qx[t] < 0 || qx[t] >= 6 || qy[t] < 0 || qy[t] >= 6)
						continue;
					if (dist[qx[t]][qy[t]] == 1000) {
						dist[qx[t]][qy[t]] = dist[qx[i]][qy[i]]+1;
						++t;
					}
				}
			}
			return dist[ex][ey] == len;
		}
		for (int i=0; i<=6; i++)
			for (int j=0; j<=6; j++) {
				// vertical wall
				if (j+l[act] <= 6) {
					wx[act] = wx2[act] = i;
					wy[act] = j;
					wy2[act] = j+l[act];
					boolean inters = false;
					for (int k=0; k<act; k++)
						if (intersect(k,act)) {
							inters = true;
							break;
						}
					if (!inters && isvalid(act) && backtrack(act+1,l,len,sx,sy,ex,ey))
						return true;
				}
				// horizontal wall
				if (i+l[act] <= 6) {
					wx[act] = i;
					wx2[act] = i+l[act];
					wy[act] = wy2[act] = j;
					boolean inters = false;
					for (int k=0; k<act; k++)
						if (intersect(k,act)) {
							inters = true;
							break;
						}
					if (!inters && isvalid(act) && backtrack(act+1,l,len,sx,sy,ex,ey))
						return true;
				}
			}
		return false;
	}
	void solve(int [] l, String path) {
		// try all start positions
		for (int sx=0; sx<6; sx++)
			for (int sy=0; sy<6; sy++) {
				for (int i=0; i<6; i++)
					for (int j=0; j<6; j++)
						onPath[i][j] = -100;
				int ex = sx;
				int ey = sy;
				onPath[sx][sy] = 0;
				boolean inside = true;
				for (int i=0; i<path.length(); i++) {
					switch(path.charAt(i)) {
						case 'N': --ex; break;
						case 'E': ++ey; break;
						case 'S': ++ex; break;
						case 'W': --ey; break;
					}
					if (ex < 0 || ex >= 6 || ey < 0 || ey >= 6) {
						inside = false;
						break;
					}
					onPath[ex][ey] = i+1;
				}
				if (inside && backtrack(0,l,path.length(),sx,sy,ex,ey)) {
					System.out.println((sy+1)+" "+(sx+1));
					System.out.println((ey+1)+" "+(ex+1));
					for (int i=0; i<3; i++)
						System.out.println(wy[i]+" "+wx[i]+" "+wy2[i]+" "+wx2[i]);
					return;
				}
			}
		// this should not happen
		System.out.println("No solution found :-(");
	}
	public static void main(String [] args) throws Exception {
		Scanner in = new Scanner(new File("construct.in"));
		int [] l = new int[3];
		while(true) {
			for (int i=0; i<3; i++)
				l[i] = in.nextInt();
			if (l[0] == 0)
				break;
			String path = in.next();
			new construct().solve(l,path);
		}
	}
}