2407.cpp

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

/* This Code is Submitted by wywcgs for Problem 2407 on 2006-10-26 at 13:46:45 */
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const int N = 16, R = 4096;
const int DIR[][2] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };

class Room {
private:
	int h, w, rn, dn;
	int label[N][N], check[R], match[R], dis[4*N][N*N];
	char map[N][N];
	bool legal(int x, int y) { return x >= 0 && x < h && y >= 0 && y < w && map[x][y] == '.'; }
	bool dfs(int, int, int);
public:
	bool build();
	int escape();
};
bool Room::build() {
	scanf("%d %d\n", &h, &w);
	for(int i = 0; i < h; i++) gets(map[i]);
	dn = rn = 0;
	int door[N*N];
	for(int i = 0; i < h; i++)
		for(int j = 0; j < w; j++)
			if(map[i][j] == '.') label[i][j] = rn++;
			else if(map[i][j] == 'D') { label[i][j] = dn++; door[dn-1] = (i<<10)|j; }
	bool vst[N][N] = { false };
	memset(dis, -1, sizeof(dis));
	for(int i = 0; i < dn; i++) {
		int dx = door[i]>>10, dy = door[i]&1023;
		queue<int> Q; Q.push((dx<<10)|dy); Q.push(0);
		while(!Q.empty()) {
			int p = Q.front(), x = p>>10, y = p&1023; Q.pop();
			int step = Q.front(); Q.pop();
			vst[x][y] = true;
			for(int j = 0; j < 4; j++) {
				int cx = x+DIR[j][0], cy = y+DIR[j][1];
				if(!legal(cx, cy)) continue;
				int rk = label[cx][cy];
				if(dis[i][rk] != -1) continue;
				dis[i][rk] = step+1; Q.push((cx<<10)|cy); Q.push(step+1);
			}
		}
	}
	for(int i = 0; i < h; i++)
		for(int j = 0; j < w; j++)
			if(map[i][j] == '.' && !vst[i][j]) return false;
	return true;
}
bool Room::dfs(int u, int t, int p) {
	for(int i = 0; i < dn; i++) {
		if(dis[i][u] == -1) continue;
		for(int j = dis[i][u]; j <= t; j++) {
			int no = (j-1)*dn+i;
			if(check[no] == p) continue;
			int k = match[no];
			match[no] = u; check[no] = p;
			if(k == -1 || dfs(k, t, p)) return true;
			match[no] = k;
		}
	}
	return false;
}
int Room::escape() {
	bool md[N*N] = { false };
	memset(match, -1, sizeof(match)); memset(check, -1, sizeof(check));
	for(int t = 1, em = 0; true; t++) {
		for(int i = 0; i < rn; i++)
			if(md[i]) continue;
			else if(dfs(i, t, t*rn+i)) { em++; md[i] = true; }
		if(em == rn) return t;
	}
}

int main()
{
	int T;
	Room r;

	scanf("%d", &T);
	for(int t = 0; t < T; t++) {
		if(!r.build()) printf("impossible\n");
		else printf("%d\n", r.escape());
	}
	
	return 0;
}