2307.cpp

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

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

const int S = 1 << 14;
const int K = 8, N = 8;
const int INF = 1 << 30;
const int DIR[][2] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 }, 
							{ 1, 1 }, { -1, -1 }, { 1, -1 }, { -1, 1 } };

int step[S][N][N], prev[S][N][N];
int bit[N][N], n;
char map[N][N+1];

inline bool legal(int x, int y) { return x >= 0 && x < N && y >= 0 && y < N; }
int bfs(int, int);
int vst(int, int);

int main()
{
	int t, T, i, j;
	
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("\n"); n = 0;
		int b, e;
		for(i = N-1; i >= 0; i--) {
			gets(map[i]);
			if(t == 428 || t == 440) { fputs(map[i], stderr); fputc('\n', stderr); }
			for(j = 0; j < N; j++)
				if(map[i][j] == 'Q') { b = j*8+i; map[i][j] = '.'; }
				else if(map[i][j] == 'B') e = j*8+i;
				else if(map[i][j] == 'N') map[i][j] = n++;
		}
		for(i = 0; i < N; i++)
			for(j = 0; j < N; j++)
				bit[i][j] = vst(i, j);
		printf("Scenario #%d:\n", t+1);
		memset(step, -1, sizeof(step));
		if(bfs(e, b) == INF) printf("impossible");
		else {
			int st = (1<<n)-1, py = b>>3, px = b&7;
			printf("%c%d", py+'a', px+1);
			while(prev[st][px][py] != -1) {
				int &pv = prev[st][px][py];
				st = pv>>6; py = (pv>>3)&7; px = pv&7;
				printf("%c%d", py+'a', px+1);
			}
		}
		printf("\n\n");
	}
	
	return 0;
}

int bfs(int b, int e)
{
	queue<int> Q;
	int i, j, by = b>>3, bx = b&7, ey = e>>3, ex = e&7, ss = (1<<n)-1;
	for(i = 0; i < K; i++) {
		int nx = bx+DIR[i][0], ny = by+DIR[i][1];
		if(!legal(nx, ny) || map[nx][ny] != '.') continue;
		Q.push((bit[nx][ny]<<6)|(ny<<3)|nx);
		step[bit[nx][ny]][nx][ny] = 0; prev[bit[nx][ny]][nx][ny] = -1;
	}
	while(!Q.empty()) {
		int p = Q.front(); Q.pop();
		int pst = p>>6, cp = p&63, py = cp>>3, px = cp&7, i;
		if(step[pst][px][py] == step[ss][ex][ey]) return step[pst][px][py];
		for(i = 0; i < K; i++) {
			for(j = 1; j < N; j++) {
				int nx = px+DIR[i][0]*j, ny = py+DIR[i][1]*j;
				if(!legal(nx, ny) || map[nx][ny] != '.') break;
				int nst = pst | bit[nx][ny];
				if(step[nst][nx][ny] == -1) {
					step[nst][nx][ny] = step[pst][px][py]+1;
					prev[nst][nx][ny] = p;
					Q.push((nst<<6)|(ny<<3)|nx);
				} else if(step[nst][nx][ny] == step[pst][px][py]+1) {
					int at = prev[nst][nx][ny], bt = p;
					while(true) {
						int ast = at>>6, ap = at&63, ay = (at>>3)&7, ax = at&7,
							bst = bt>>6, bp = bt&63, by = (bt>>3)&7, bx = bt&7;
						if(ap != bp) {
							if(ap > bp) prev[nst][nx][ny] = p;
							break;
						} else { at = prev[ast][ax][ay]; bt = prev[bst][bx][by]; }
					}
				}
			}
		}
	}
	return INF;
}
int vst(int x, int y)
{
	int i, s = 0;
	for(i = 0; i < K; i++) {
		int nx = x+DIR[i][0], ny = y+DIR[i][1];
		if(!legal(nx, ny) || map[nx][ny] >= n) continue;
		s |= 1 << map[nx][ny];
	}
	return s;
}