basic.cpp

Ulm大学2005-2006年竞赛题

// Problem   Basic wall maze
// Algorithm breadth first search
// Author    Adrian Kuegel
// Date      2006.07.08

#include <iostream>
#include <fstream>
#include <queue>
#include <assert.h>
#include <utility>
#include <string>
#include <algorithm>
using namespace std;

typedef pair<int,int> PII;

int dirs[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
char dirname[5] = "NESW";

int main() {
	ifstream in("basic.in");
	int sx,sy,ex,ey;
	while(in >> sy >> sx && (sy != 0 || sx != 0)) {
		assert(sx > 0 && sx <= 6 && sy > 0 && sy <= 6);
		in >> ey >> ex;
		assert(ex > 0 && ex <= 6 && ey > 0 && ey <= 6);
		assert(ex != sx || ey != sy);
		// represent the grid as 6 x 6 squares separated by borders
		// -> 13 x 13 grid, borders at even rows/columns (0 to 12)
		bool visit[13][13] = {{}}; // initialized to false
		int prev[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;
			in >> x1 >> y1 >> x2 >> y2;
			assert(x1 == x2 || y1 == y2);
			assert(x1 >= 0 && x1 <= 6 && y1 >= 0 && y1 <= 6);
			assert(x2 >= 0 && x2 <= 6 && y2 >= 0 && y2 <= 6);
			assert(x1 < x2 || y1 < y2);
			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
		queue<PII> Q;
		sx = sx*2-1;
		sy = sy*2-1;
		ex = ex*2-1;
		ey = ey*2-1;
		Q.push(PII(sx,sy));
		while(!Q.empty()) {
			PII cur = Q.front();
			Q.pop();
			for (int d=0; d<4; d++) {
				PII next(cur.first+dirs[d][0],cur.second+dirs[d][1]);
				if (!visit[next.first][next.second]) {
					visit[next.first][next.second] = true;
					prev[next.first][next.second] = d;
					Q.push(next);
				}
			}
		}
		assert(visit[ex][ey]);
		string path = "";
		do {
			int cur_dir = prev[ex][ey];
			if (ex % 2 != 0 && ey % 2 != 0)
				path += dirname[cur_dir];
			ex -= dirs[cur_dir][0];
			ey -= dirs[cur_dir][1];
		}while(sx != ex || sy != ey);
		reverse(path.begin(),path.end());
		cout << path << endl;
	}
	assert(sx == 0 && sy == 0);
	return 0;
}