construct_naive.cpp

Ulm大学2005-2006年竞赛题

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

#include <stdio.h>
#include <assert.h>
#include <algorithm>
#include <string>
#include <utility>
#include <queue>
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 wallx[3],wally[3],wallx2[3],wally2[3];
char walldir[3];

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 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];
int find_shortest_path() {
	// do a breadth first search to find the shortest path
	queue<PII> Q;
	memset(dist,0,sizeof(dist));
	Q.push(PII(startx * 2 + 1, starty * 2 + 1));
	while(!Q.empty()) {
		PII t = Q.front();
		Q.pop();
		for (int d=0; d<4; d++) {
			int tx = t.first + dx[d];
			int ty = t.second + dy[d];
			if (tx > 0 && tx < DIMENSION*2 && ty > 0 && ty < DIMENSION*2 && !dist[tx][ty] && flag[tx][ty]>=0) {
				dist[tx][ty] = dist[t.first][t.second] + 1;
				if (tx == endx*2+1 && ty == endy*2+1)
					return 1;
				Q.push(PII(tx,ty));
			}
		}
	}
	return 0;
}

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;
	}
	for (int x=0; x<=DIMENSION; x++) {
		for (int y=0; y<=DIMENSION; y++) {
			wallx[cur] = x;
			wally[cur] = y;
			// try vertical wall
			if (x + len[cur] <= DIMENSION) {
				wallx2[cur] = x+len[cur];
				wally2[cur] = y;
				walldir[cur] = 1;
				// 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);
				}
			}
			if (y + len[cur] <= DIMENSION) {
				// try horizontal wall
				wallx2[cur] = x;
				wally2[cur] = y+len[cur];
				walldir[cur] = 0;
				// 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],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);
		}
		memset(flag,0,sizeof(flag));
		int diffx = curx;
		int diffy = cury;
		// 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
		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;
				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;
}