1838.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1838 on 2006-02-17 at 11:59:07 */ 
#include <cstdio>
#include <cctype>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX = 327680;
const int L_MAX = 6;
const int N_MAX = 16;
const int DIR[][2] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
typedef pair<int, int> pii;

class BitVector {
private:
	unsigned int bit[MAX];
public:
	void clear();
	bool test(int) const;
	void set(int);
};
void BitVector::clear() {
	memset(bit, 0, sizeof(bit));
}
bool BitVector::test(int pos) const {
	return (bit[pos>>5]&(1<<(pos&31))) != 0;
}
void BitVector::set(int pos) {
	bit[pos>>5] |= 1 << (pos & 31);
}

BitVector vst;
bool vehdir[N_MAX];
int pos[N_MAX][2], len[N_MAX], n;
char field[L_MAX][L_MAX+1];

inline int code(char);
inline int& sub(int o) { return vehdir[o] ? pos[o][0] : pos[o][1]; }
inline int& obj(int o) { return vehdir[o] ? pos[o][1] : pos[o][0]; }
inline void push(queue<pii>&, int, int);
inline bool legal(int, int);
int hash();
void unhash(int);
int move(int);

int main()
{
	int i, j, t;

	for(t = 1; scanf("%d\n", &n) != EOF && n != 0; t++) {
		for(i = 0; i < L_MAX; i++) gets(field[i]);
		memset(len, -1, sizeof(len));
		for(i = 0; i < L_MAX; i++) {
			for(j = 0; j < L_MAX; j++) {
				int o = code(field[i][j]);
				if(o >= 0 && len[o] == -1) {
					vehdir[o] = (field[i][j+1] == field[i][j]);
					pos[o][0] = i; pos[o][1] = j;
					if(vehdir[o]) for(len[o] = 1; field[i][j+len[o]] == field[i][j]; len[o]++);
					else for(len[o] = 1; field[i+len[o]][j] == field[i][j]; len[o]++);
				}
			}
		}
		int step = move(hash());
		if(step == MAX) printf("You are trapped in scenario #%d.\n", t);
		else printf("Scenario #%d requires %d moves.\n", t, step);
	}
	
	return 0;
}

inline int code(char o)
{
	if(o == 'x') return n-1;
	else if(isalpha(o)) return o - 'a';
	else return -1;
}
int hash()
{
	int i, state;
	for(state = i = 0; i < n; i++)
		state = state * 5 + obj(i);
	return state;
}
void unhash(int state)
{
	int i, j;
	for(i = 0; i < n; i++, state /= 5)
		obj(n-1-i) = state % 5;
	memset(field, '.', sizeof(field));
	for(i = 0; i < n; i++) {
		int r = pos[i][0], c = pos[i][1];
		for(j = 0; j < len[i]; j++)
			if(vehdir[i]) field[r][c+j] = 'a' + i;
			else field[r+j][c] = 'a' + i;
	}
}
int move(int begin)
{
	queue<pii> Q; int i, j;
	vst.clear();
	vst.set(begin); Q.push(pii(begin, 0));
	while(!Q.empty()) {
		pii p = Q.front(); Q.pop();
		unhash(p.first);
		if(pos[n-1][1] == L_MAX-len[n-1]) return p.second;
		for(i = 0; i < n; i++) {
			for(j = 1; legal(i, j); j++) { obj(i) += j; push(Q, hash(), p.second); obj(i) -= j; }
			for(j = -1; legal(i, j); j--) { obj(i) += j; push(Q, hash(), p.second); obj(i) -= j; }
		}
	}
	
	return MAX;
}
inline void push(queue<pii>& Q, int state, int step)
{
	if(vst.test(state)) return;
	Q.push(pii(state, step+1)); vst.set(state);
}
inline bool legal(int o, int step)
{
	int r = pos[o][0], c = pos[o][1], &x = vehdir[o] ? c : r;
	x += step;
	if(step > 0) x += len[o]-1;
	if(x < 0 || x >= L_MAX) return false;
	return field[r][c] == '.';
}