construct.cpp

Ulm大学2005-2006年竞赛题

// Problem   Construct the maze
// Algorithm backtracking / breadth first search
// Runtime   O(n^4) (n is number of grid squares)
// Author    Adrian Kuegel
// Date      2006.06.16

#include <stdio.h>
#include <assert.h>
#include <algorithm>
#include <string>
using namespace std;

#define DIMENSION 6

typedef pair<int,int> PII;

int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
char dir_name[5] = "NESW";

int len[3];
char path[60];
char flag[DIMENSION*2+1][DIMENSION*2+1]; /* value < 0 means blocked by a wall
				    	  * value = 0 means free
					  * value 1 means part of the shortest path
					  */
int startx,starty,endx,endy;
int leftx,rightx,lefty,righty;
int wallx[3],wally[3],wallx2[3],wally2[3];
char walldir[3];

int do_mark(int x, int y, int len, int d) {
	len *= 2;
	x *= 2;
	y *= 2;
	int sx = x, sy = y;
	// first check if it is possible to place a wall
	for (int i=0; i<=len && x<=DIMENSION*2 && y<=DIMENSION*2; i++) {
		if (flag[x][y] == 1)
			return 0;
		x += dx[d];
		y += dy[d];
	}
	x = sx;
	y = sy;
	// now mark wall positions
	for (int i=0; i<=len && x<=DIMENSION*2 && y<=DIMENSION*2; i++) {
		--flag[x][y];
		x += dx[d];
		y += dy[d];
	}
	return 1;
}

void unmark(int x, int y, int len, int d) {
	len *= 2;
	x *= 2;
	y *= 2;
	for (int i=0; i<=len && x<=DIMENSION*2 && y<=DIMENSION*2; i++) {
		++flag[x][y];
		x += dx[d];
		y += dy[d];
	}
}

int dist[DIMENSION*2+1][DIMENSION*2+1],q[(DIMENSION*2+1)*(DIMENSION*2+1)][2];

int find_shortest_path() {
	// do a breadth first search to find the shortest path
	memset(dist,0,sizeof(dist));
	q[0][0] = startx*2 + 1;
	q[0][1] = starty*2 + 1;
	int l = 1;
	for (int i=0; i<l; i++) {
		for (int d=0; d<4; d++) {
			int tx = q[i][0] + dx[d];
			int ty = q[i][1] + dy[d];
			if (tx > 0 && tx < DIMENSION*2 && ty > 0 && ty < DIMENSION*2 && !dist[tx][ty] && flag[tx][ty]>=0) {
				dist[tx][ty] = dist[q[i][0]][q[i][1]] + 1;
				if (tx == endx*2+1 && ty == endy*2+1)
					return 1;
				q[l][0] = tx;
				q[l][1] = ty;
				++l;
			}
		}
	}
	return 0;
}

// values for corners (for placing unused walls)
int cx[4] = {0,0,0,DIMENSION};
int cy[4] = {0,0,DIMENSION,0};
int cd[4] = {1,2,2,1};

int intersect(int a, int b) {
	if (walldir[a] == walldir[b]) {
		if (walldir[a]) // vertical walls
			return wally[a] == wally[b] && max(wallx[a],wallx[b]) < min(wallx[a]+len[a],wallx[b]+len[b]);
		// horizontal walls
		return wallx[a] == wallx[b] && max(wally[a],wally[b]) < min(wally[a]+len[a],wally[b]+len[b]);
	}
	if (!walldir[a])
		swap(a,b);
	return wallx[a] > wallx[b] && wallx[a] < wallx[b]+len[b]
		&& wally[b] > wally[a] && wally[b] < wally[a]+len[a];
}

int backtrack(int cur) {
	if (cur == 3) {
		if (find_shortest_path() && dist[endx*2+1][endy*2+1]/2 == (int)strlen(path)) { // solution found
			// print the solution
			printf("%d %d\n",starty+1,startx+1);
			printf("%d %d\n",endy+1,endx+1);
			for (int i=0; i<3; i++)
				printf("%d %d %d %d\n",wally[i],wallx[i],wally2[i],wallx2[i]);
			return 1;
		}
		return 0;
	}
	// first try to place the wall at the boarder of the grid -> unused wall
	for (int i=0; i<4; i++) {
		if (do_mark(cx[i],cy[i],len[cur],cd[i])) {
			wallx[cur] = cx[i];
			wally[cur] = cy[i];
			walldir[cur] = cd[i]-1;
			if (walldir[cur]) {
				wallx2[cur] = cx[i]+len[cur];
				wally2[cur] = cy[i];
			}
			else {
				wallx2[cur] = cx[i];
				wally2[cur] = cy[i]+len[cur];
			}
			bool inters = false;
			for (int j=0; j<cur; j++)
				if (intersect(j,cur)) {
					inters = true;
					break;
				}
			if (!inters && backtrack(cur+1))
				return 1;
			unmark(cx[i],cy[i],len[cur],cd[i]);
			if (!inters)
				break;
		}
	}
	// now make sure that the wall intersects the interval of path coordinates
	for (int x=0; x<=DIMENSION; x++) {
		if (max(x*2,leftx*2+1) >= min((x+len[cur])*2, rightx*2+1))
			continue;
		for (int y=0; y<=DIMENSION; y++) {
			if (max(y*2,lefty*2+1) >= min((y+len[cur])*2, righty*2+1))
				continue;
			wallx[cur] = x;
			wally[cur] = y;
			// try vertical wall
			// check that the wall intersects the interval of path coordinates
			if (x+len[cur] <= DIMENSION && y*2 >= lefty*2+1 && y*2 <= righty*2+1) {
				walldir[cur] = 1;
				wallx2[cur] = x+len[cur];
				wally2[cur] = y;
				// check for intersections
				bool inters = false;
				for (int i=0; i<cur; i++)
					if (intersect(i,cur)) {
						inters = true;
						break;
					}
				if (!inters && do_mark(x,y,len[cur],2)) {
					if (backtrack(cur+1))
						return 1;
					unmark(x,y,len[cur],2);
				}
			}
			// try horizontal wall
			if (y+len[cur] <= DIMENSION && x*2 >= leftx*2+1 && x*2 <= rightx*2+1) {
				walldir[cur] = 0;
				wallx2[cur] = x;
				wally2[cur] = y+len[cur];
				bool inters = false;
				for (int i=0; i<cur; i++)
					if (intersect(i,cur)) {
						inters = true;
						break;
					}
				if (!inters && do_mark(x,y,len[cur],1)) {
					if (backtrack(cur+1))
						return 1;
					unmark(x,y,len[cur],1);
				}
			}
		}
	}
	return 0;
}

int main() {
	freopen("construct.in","r",stdin);
	while(scanf("%d %d %d",len,len+1,len+2) == 3 && (len[0] || len[1] || len[2])) {
		assert(len[0] > 0 && len[1] > 0 && len[2] > 0);
		assert(scanf("%s",path) == 1);
		assert(strlen(path) <= (DIMENSION-1)*5);
		// first determine a valid starting position, with biggest row / column
		int maxx = 0, minx = 0;
		int maxy = 0, miny = 0;
		int curx = 0,cury = 0;
		for (int i=0; path[i]; i++) {
			int d;
			for (d=0; dir_name[d]; d++)
				if (dir_name[d] == path[i])
					break;
			assert(d < 4);
			curx += dx[d];
			cury += dy[d];
			maxx = max(curx,maxx);
			maxy = max(cury,maxy);
			minx = min(curx,minx);
			miny = min(cury,miny);
		}
		int diffx = curx;
		int diffy = cury;
		bool found = false;
		for (startx = -minx; startx <= DIMENSION-1-maxx; startx++) {
			for (starty = -miny; starty <= DIMENSION-1-maxy; starty++) {
				endx = startx + diffx;
				endy = starty + diffy;
				leftx = startx+minx;
				rightx = startx+maxx;
				lefty = starty+miny;
				righty = starty+maxy;
				assert(leftx >= 0 && rightx < DIMENSION);
				assert(lefty >= 0 && righty < DIMENSION);
				memset(flag,0,sizeof(flag));
				// transform the grid into a grid of size 13 by 13
				// grid squares are at odd positions, walls are at even positions
				// mark the squares of the path
				curx = startx*2 + 1;
				cury = starty*2 + 1;
				flag[curx][cury] = 1;
				for (int i=0; path[i]; i++) {
					int d;
					for (d=0; dir_name[d]; d++)
						if (dir_name[d] == path[i])
							break;
					assert(d < 4);
					curx += dx[d];
					cury += dy[d];
					flag[curx][cury] = 1;
					curx += dx[d];
					cury += dy[d];
					flag[curx][cury] = 1;
				}
				// now find a solution using backtracking
				if (backtrack(0)) {
					found = true;
					goto done;
				}
			}
		}
		done: assert(found);
	}
	assert(len[0] == 0 && len[1] == 0 && len[2] == 0);
	return 0;
}