Evacuation POJ - 3057（二分匹配）

Fires can be disastrous, especially when a fire breaks out in a room that is completely filled with people. Rooms usually have a couple of exits and emergency exits, but with everyone rushing out at the same time, it may take a while for everyone to escape.

You are given the floorplan of a room and must find out how much time it will take for everyone to get out. Rooms consist of obstacles and walls, which are represented on the map by an ‘X’, empty squares, represented by a ‘.’ and exit doors, which are represented by a ‘D’. The boundary of the room consists only of doors and walls, and there are no doors inside the room. The interior of the room contains at least one empty square.

Initially, there is one person on every empty square in the room and these persons should move to a door to exit. They can move one square per second to the North, South, East or West. While evacuating, multiple persons can be on a single square. The doors are narrow, however, and only one person can leave through a door per second.

What is the minimal time necessary to evacuate everybody? A person is evacuated at the moment he or she enters a door square.

Input

The first line of the input contains a single number: the number of test cases to follow. Each test case has the following format:

One line with two integers Y and X, separated by a single space, satisfying 3 <= Y, X <= 12: the size of the room Y lines with X characters, each character being either ‘X’, ‘.’, or ‘D’: a valid description of a room

Output
For every test case in the input, the output should contain a single line with the minimal evacuation time in seconds, if evacuation is possible, or “impossible”, if it is not.

Sample Input
3
5 5
XXDXX
X…X
D…X
X…D
XXXXX
5 12
XXXXXXXXXXXX
X…D
X.XXXXXXXXXX
X…X
XXXXXXXXXXXX
5 5
XDXXX
X.X.D
XX.XX
D.X.X
XXXDX

Sample Output
3
21
impossible

题意：
墙壁（“X”），人（“.”）， 门（“D”）。
人向门移动通过时视为逃脱，门每秒能出去一个人，人可以上下左右移动，不可穿墙。
求最优移动方案下，最后一个人逃脱的最短时间。如果有人无法安全逃脱（比如被墙围困住），则输出“impossible”。

题解：
由于每秒每个门只能出去一人，如果只是考虑离门最远一个人离开的时间，不能做到在这之前所有人都出去了。
例如
XXDXX
X . . . X
XXXXX
这种情况下，离门最远一个人离开的时间是 2秒，但是2秒只能出去一人，所以总共时间为3秒

根据条件：每秒每个门只能出去一人，可知时间和门是相关的。也就是说，1s时刻的门和2s时刻的门是不一样的（不一样在于，一秒时刻人的集合与两秒时刻，人在移动，还未出门的人的集合不一样，即一个人在一秒时刻与两秒时刻通过某扇门的意义是不一样的，属于不同的匹配）。

这个题的难点在于建图，（《挑程》上说）每个时间和门的二元组 和 人 组成的二分图的匹配数，可以判断所有人是否都能够逃脱。
也就是说，三个变量： 哪扇门 什么时刻 那个人
而《挑程》上，把前两个变量一起考虑，也就是把人作为一个集合，把门和时间，作为一个集合，如果任何情况下第一个集合中的 人 不能全被匹配，则说明有一些人无法逃脱，输出“impossible”

否则肯定有一个最短时间能让所有人逃脱。从第一秒开始遍历时间，构出一个 人 与 门 的二分图，求最大匹配，如果匹配数 == 人数，那么这就是最短的时间。

注意时间遍历的上限为为 X * Y（X为行数，Y为列数， 最长时间max_t 一定 小于 XY, 但是没关系， 如果所有人可以出来，在最长时间 max_t 时，逃脱人数 就等于 所有人，输出；如果所有人没法出来，那时间再长，都不可能所有人都出来）

我的二分匹配模板：
https://blog.csdn.net/rainbowsea_1/article/details/106221614

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;const int MAX_X = 13;
const int MAX_Y = 13;
const int MAX_V = 13 * 13 * 13 * 13;
const int DX[] = {0, 1, -1, 0};
const int DY[] = {1, 0, 0, -1};
char field[MAX_X][MAX_Y];
int dist[MAX_X][MAX_Y][MAX_X][MAX_Y];
vector<int>dx, dy;
vector<int>px, py;
vector<int>G[MAX_V];
int match[MAX_V];
bool used[MAX_V];
int Y, X;
//添加点
void add_edge(int u, int v) {G[u].push_back(v);G[v].push_back(u);
}
//二分匹配
bool dfs(int v) {used[v] = true;for (int i = 0; i < G[v].size(); i++) {int u = G[v][i], w = match[u];if ( w < 0 || !used[w] && dfs(w)) {match[v] = u;match[u] = v;return true;}}return false;
}void bfs(int x, int y, int d[MAX_X][MAX_Y]) {
//D(门)与人的最短距离，编辑的是dist[][]([][]这两个)queue<int>qx, qy;d[x][y] = 0;qx.push(x);qy.push(y);while(qx.size()) {x = qx.front(), y = qy.front();qx.pop(), qy.pop();for(int i = 0; i < 4; i++) {int x2 = x + DX[i], y2 = y + DY[i];if(x2 >= 0 && x2 < X && y2 >= 0 && y2 < Y && field[x2][y2] == '.' && d[x2][y2] < 0) {d[x2][y2] = d[x][y] + 1;qx.push(x2);qy.push(y2);}}}
}void solve() {memset(dist, -1, sizeof(dist));dx.clear();dy.clear();px.clear();py.clear();for(int ix = 0; ix < X; ix++){for(int iy = 0; iy < Y; iy++) {if(field[ix][iy] == 'D') {dx.push_back(ix);dy.push_back(iy);bfs(ix, iy, dist[ix][iy]);}else if(field[ix][iy] == '.') {px.push_back(ix);py.push_back(iy);}}}int n = X * Y;int d = dx.size(), p = px.size();for(int v = 0; v < n * d; v++) G[v].clear();for(int i = 0; i < d; i++) {for(int j = 0; j < p; j++) {if(dist[dx[i]][dy[i]][px[j]][py[j]] >= 0) {//时间区间：某个门到某个点(人)的最短时间 ~ n =  X * Yfor(int k = dist[dx[i]][dy[i]][px[j]][py[j]]; k <= n; k++) {//匹配方法：k时刻只有一个人px[j]py[j]能从门dx[i]dy[j]逃走//d = 人数 时间1对应 0 ~ d - 1的门， 时间k 对应 (k - 1)*d + 1 ~ k*d - 1add_edge((k - 1) * d + i, n * d + j);}}}}if(p == 0) {printf("0\n");return;}int num = 0;memset(match, -1, sizeof(match));for(int i = 0; i < n * d; i++) {memset(used, 0, sizeof(used));if(dfs(i)) {num++;if(num == p) {printf("%d\n", i / d + 1);return;}}}printf("impossible\n");return;
}int main() {int T;scanf("%d", &T);while(T--) {scanf("%d%d", &X, &Y);for(int i = 0; i < X; i++) {scanf("%s", field[i]); //cout << field[i] << endl;}solve();}
}