每个门每个时间只能出一个人，那就把每个门拆成多个，对应每个时间。
不断增加时间，然后增广，直到最大匹配。
//#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<iostream> #include<sstream> #include<cmath> #include<climits> #include<string> #include<map> #include<queue> #include<vector> #include<stack> #include<set> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; #define pb(a) push(a) #define INF 0x1f1f1f1f #define lson idx<<1,l,mid #define rson idx<<1|1,mid+1,r #define PI 3.1415926535898 template<class T> T min(const T& a,const T& b,const T& c) { return min(min(a,b),min(a,c)); } template<class T> T max(const T& a,const T& b,const T& c) { return max(max(a,b),max(a,c)); } void debug() { #ifdef ONLINE_JUDGE #else freopen("data.in","r",stdin); // freopen("d:\out1.txt","w",stdout); #endif } int getch() { int ch; while((ch=getchar())!=EOF) { if(ch!=' '&&ch!=' ')return ch; } return EOF; } int DX[] = {0, 1, 0, -1}; int DY[] = {1, 0, -1, 0}; const int maxn = 15; char grid[maxn][maxn]; int n, m; int dist[maxn][maxn][maxn][maxn]; int vis[maxn][maxn]; vector<int> dx,dy,px,py; void bfs(int X,int Y) { queue<int> qx,qy; qx.push(X); qy.push(Y); memset(vis, 0, sizeof(vis)); vis[X][Y] = true; while(!qx.empty()) { int x = qx.front(); qx.pop(); int y = qy.front(); qy.pop(); for(int d=0; d<4; d++) { int nx = x + DX[d]; int ny = y + DY[d]; if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&grid[nx][ny]=='.'&&!vis[nx][ny]) { vis[nx][ny] = true; dist[X][Y][nx][ny] = dist[X][Y][x][y] + 1; qx.push(nx); qy.push(ny); } } } } void prework() { memset(dist, -1, sizeof(dist)); dx.clear(); dy.clear(); px.clear(); py.clear(); for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) { if(grid[i][j]=='D') { dx.push_back(i); dy.push_back(j); dist[i][j][i][j]=0; bfs(i, j); }else if(grid[i][j]=='.') { px.push_back(i); py.push_back(j); } } //printf("prework: %d %d ",dx.size(), px.size()); } const int maxv = 101*50 + 110; int id[maxn][maxn][110]; bool used[maxv]; int match[maxv]; int vcnt; vector<int> g[maxv]; int ID(int x, int y, int t) { int &a = id[x][y][t]; if(a==0) a=++vcnt; return a; } void add(int u,int v) { g[u].push_back(v); g[v].push_back(u); } void init() { for(int i=1; i<maxv; i++) g[i].clear(); memset(id, 0, sizeof(id)); } bool dfs(int u) { used[u] = true; for(int i = 0; i < g[u].size(); i++) { int v = g[u][i]; int w = match[v]; if(w<0||!used[w]&&dfs(w)) { match[u] = v; match[v] = u; return true; } } return false; } int solve() { init(); memset(match, -1, sizeof(match)); int res = 0; vcnt = 0; if(px.size() == 0) return 0; for(int t=1; t<=100; t++) { for(int i=0; i<dx.size(); i++) { for(int j=0; j<px.size(); j++) { int dis = dist[dx[i]][dy[i]][px[j]][py[j]]; if(dis!=-1 && dis <= t) { int u = ID(dx[i], dy[i], t); int v = ID(px[j], py[j], 0); add(u, v); add(v, u); } } } for(int i=0; i<dx.size(); i++) { int u = ID(dx[i], dy[i], t); memset(used, 0, sizeof(used)); if(dfs(u)) res++; } if(res == px.size()) return t; } return -1; } int main() { debug(); int t; scanf("%d", &t); for(int ca=1; ca<=t; ca++) { scanf("%d%d", &n, &m); for(int i=1; i<=n; i++) scanf("%s", grid[i]+1); prework(); int ans = solve(); if(ans != -1) printf("%d ", ans); else printf("impossible "); } return 0; }