1390.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/* This Code is Submitted by wywcgs for Problem 1390 on 2007-03-26 at 20:38:12 */
#include <cstdio>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;

typedef long long int64;
const int N = 9;
const int HSIZE = 799999;
const int DIR[][2] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
const char DIR_STR[][8] = { "north", "east", "south", "west" };

class HashTable {
private:
	int64 value[HSIZE], key[HSIZE];
	int hash(int64 v) const { return v%HSIZE; }
public:
	void clear() { memset(value, -1, sizeof(value)); }
	void insert(int64, int64);
	int64 find(int64) const;
};
void HashTable::insert(int64 v, int64 k) {
	for(int i = hash(v); true; i++) {
		if(i == HSIZE) i = 0;
		if(value[i] == -1) { value[i] = v; key[i] = k; return; }
		else if(value[i] == v) return;
	}
}
int64 HashTable::find(int64 v) const {
	for(int i = hash(v); true; i++) {
		if(i == HSIZE) i = 0;
		if(value[i] == -1) return -1;
		else if(value[i] == v) return key[i];
	}
}

class Data {
public:
	int esn, tsn;
	int64 status, prev;
	Data(int ce, int ct, int64 cs, int64 cp) 
		: esn(ce), tsn(ct), status(cs), prev(cp) {}
	bool operator >(const Data& d) const { return esn > d.esn || (esn == d.esn && status > d.status); }
};

class Maze {
private:
	char maze[N][N];
	int n, minStep[N][N];
	int64 source[4][N*N];
	HashTable ht;
	void findPath(int64, int64);
	void initLimit();
	void bfs(int, int);
	void initSource();
	int statusLimit(int64) const;
public:
	bool make();
	void walk();
};
bool Maze::make() {
	if(scanf("%d", &n) != 1) return false;
	for(int i = 0; i < n; i++) scanf("%s", maze[i]);
	ht.clear();
	return true;
}
void Maze::initLimit() {
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			minStep[i][j] = N*N;
	for(int i = 0; i < n; i++) {
		if(maze[0][i] == '.') bfs(0, i);
		if(maze[n-1][i] == '.') bfs(n-1, i);
		if(maze[i][0] == '.') bfs(i, 0);
		if(maze[i][n-1] == '.') bfs(i, n-1);
	}
}
void Maze::bfs(int bx, int by) {
	int step[N][N];
	memset(step, -1, sizeof(step));
	queue<int> Q;
	Q.push(bx); Q.push(by); step[bx][by] = 0;
	while(!Q.empty()) {
		int x = Q.front(); Q.pop();
		int y = Q.front(); Q.pop();
		for(int i = 0; i < 4; i++) {
			int cx = x+DIR[i][0], cy = y+DIR[i][1];
			if(cx < 0 || cx >= n || cy < 0 || cy >= n 
				|| step[cx][cy] != -1 || maze[cx][cy] == 'O') continue;
			step[cx][cy] = step[x][y]+1;
			Q.push(cx); Q.push(cy);
		}
	}
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			if(maze[i][j] == '.') minStep[i][j] <?= step[i][j];
}
int Maze::statusLimit(int64 s) const {
	int step = 0, a = n*n;
	for(int i = 0; i < a; i++)
		if(s&(1LL<<i)) step >?= minStep[i/n+1][i%n+1];
	return step;
}
void Maze::initSource() {
	memset(source, 0, sizeof(source));
	for(int d = 0; d < 4; d++)
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++) {
				int x = i+DIR[d][0], y = j+DIR[d][1], ocd = i*n+j, ncd = x*n+y;
				if(maze[x+1][y+1] == 'O') source[d][ocd] |= 1LL << ocd;
				else if(x >= 0 && x < n && y >= 0 && y < n)
					source[d][ncd] |= 1LL << ocd;
			}
}
void Maze::findPath(int64 b, int64 e) {
	int bd = statusLimit(b);
	priority_queue< Data, vector<Data>, greater<Data> > Q;
	Q.push(Data(bd, 0, b, -1));
	int a = n*n, elimit = 1 << 20;
	while(!Q.empty()) {
		Data p = Q.top(); Q.pop();
		int64 s = p.status, prev = p.prev;
		if(ht.find(s) != -1) continue;
		ht.insert(s, prev);
		if(s == e) return;
		for(int d = 0; d < 4; d++) {
			int64 ns = 0;
			for(int i = 0; i < a; i++)
				if(s&source[d][i]) ns |= 1LL << i;
			if(ht.find(ns) != -1) continue;
			int nd = statusLimit(ns), esn = p.tsn+1+nd;
			if(esn >= elimit) continue;
			Q.push(Data(esn, p.tsn+1, ns, (s<<2)|d));
			if(ns == e) elimit <?= esn;
		}
	}
}
void Maze::walk() {
	if(n <= 2) return;
	initLimit();
	int64 b = 0; n -= 2;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			if(maze[i+1][j+1] == '.') b |= 1LL << (i*n+j);
	initSource();
	if(b != 0) findPath(b, 0);
	vector<int> dirs;
	for(int64 i = 0; i != b; i = ht.find(i)>>2)
		dirs.push_back(ht.find(i)&3);
	for(int i = dirs.size()-1; i >= 0; i--) printf("%s\n", DIR_STR[dirs[i]]);
}

Maze m;

int main()
{
	for(int t = 0; m.make(); t++) {
		if(t != 0) printf("\n");
		m.walk();
	}
	return 0;
}