POJ_3057.cpp

#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int SIZE=15;
const int MAXN=22500;
const int dx[]={0, -1, 1, 0};
const int dy[]={-1, 0, 0, 1};

vector<int> Dx, Dy;
vector<int> Px, Py;
vector<int> G[MAXN];
int match[SIZE*SIZE], vis[SIZE*SIZE];
int dis[SIZE][SIZE][SIZE][SIZE];
char map[SIZE][SIZE];
int X, Y;

void bfs(int x, int y, int d[SIZE][SIZE]) {
	queue<int> qx, qy; 
	d[x][y]=0; qx.push(x); qy.push(y);
	while (!qx.empty()) {
		x=qx.front(); qx.pop();
		y=qy.front(); qy.pop();
		for (int k=0; k<4; k++) {
			int xx=x+dx[k], yy=y+dy[k];
			if (xx<0||xx>=X||yy<0||yy>=Y||map[xx][yy]!='.'||d[xx][yy]!=-1) continue;
			d[xx][yy]=d[x][y]+1;
			qx.push(xx); qy.push(yy);
		}
	}
}

void init() {
	scanf("%d%d", &X, &Y);
	Px.clear(); Py.clear(); Dx.clear(); Dy.clear();
	for (int i=0; i<X; i++) scanf("%s", map[i]);
	memset(dis, -1, sizeof(dis));
	for (int i=0; i<X; i++)
		for (int j=0; j<Y; j++) {
			if (map[i][j]=='D') {
				Dx.push_back(i); Dy.push_back(j);
				bfs(i, j, dis[i][j]);
			}
			else if (map[i][j]=='.') {
				Px.push_back(i); Py.push_back(j);
			}
		}
}

inline void addedge(int u, int v) {
	G[u].push_back(v);
}

bool find(int u) {
	for (int v, i=0; i<(int)G[u].size(); i++) 
		if (!vis[v=G[u][i]]) {
			vis[v]=true;
			if (match[v]==-1||find(match[v])) {
				match[v]=u; return true;
			}
		}
	return false;
}

void solve() {
	init();
	int d=Dx.size(), p=Px.size(), n=X*Y;
	for (int i=0; i<=d*n; i++) G[i].clear();
	for (int i=0; i<d; i++)
		for (int j=0; j<p; j++)
			if (dis[Dx[i]][Dy[i]][Px[j]][Py[j]]>=0) {
				for (int k=dis[Dx[i]][Dy[i]][Px[j]][Py[j]]; k<=n; k++)
					addedge((k-1)*d+i, j);
			}
	if (p==0) {puts("0");return;}
	memset(match, -1, sizeof(match));
	int cnt=0;
	for (int i=0; i<d*n; i++) {
		memset(vis, 0, sizeof(vis));
		if (find(i)) {
			if (++cnt==p) {
				printf("%d\n", i/d+1);
				return;
			}
		}
	}
	printf("impossible\n");
}

int main() {
	int T; scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}