题目大意：
在一个n*m的房间中 ‘X’为墙 ‘D’为门 ‘.’为人
门只存在与外围 人每秒钟只能向四连通区域走一步
门比较狭窄 每秒钟只能通过一个人
求所有人逃脱的最短时间 如果不可能则输出impossible
对每个门 广搜出能在这个门逃脱的人的逃出时间
将 对应各个时间的这个门 当做不同的点
即 若有d个门 p个人
时间1对应的门编号为 0~d-1
时间2对应的门编号为 d~2*d-1
时间t对应的门编号为 (t-1)*d~t*d-1
然后将人编号为 t*d~t*d+p-1
再将 对应时间的门的编号 与 对应时间在该门逃脱的人 连边
而一个人若能在 t 时间逃脱 那么同样可以在 t+1、t+2、t+3...时间逃脱
所以 对应时间到最晚时间的该门的编号 都可与 这个人连边
这样找到 各个时间的门 与 人 的最大匹配
时间从小到大 这样判断到最大匹配数恰好等于人数时说明此时所有人都可逃脱
#include <bits/stdc++.h>
using namespace std;
int n,m;
char G[][];
int mov[][]={,,,,,-,-,}; int dis[][][][];
// dis[x][y][i][j] 门的位置为xy 人的位置为ij 保存逃脱的最短用时
struct NODE { int x,y; };
vector <NODE> D, P; // D记录门的位置 P记录人的位置 const int E=***;
vector <int> e[E]; // 邻接表 bool bound(int x1,int y1) {
return x1< || x1>=n || y1< || y1>=m;
}
void bfs(int x1,int y1,int d[][]) {
// d为dis[x1][y1]对应的后两维
queue <NODE> q;
q.push((NODE){x1,y1});
d[x1][y1]=;
while(!q.empty()) {
NODE e=q.front(); q.pop();
for(int i=;i<;i++) {
int x2=e.x+mov[i][], y2=e.y+mov[i][];
if(bound(x2,y2) || d[x2][y2]!=-) continue;
if(G[x2][y2]!='.') continue;
d[x2][y2]=d[e.x][e.y]+;
q.push((NODE){x2,y2});
}
}
}
/**二分图最大匹配*/
bool vis[E];
int mat[E];
bool dfs(int u) {
vis[u]=;
for(int i=;i<e[u].size();i++) {
int v=e[u][i], d=mat[v];
if(d==- || !vis[d]&&dfs(d)) {
mat[u]=v, mat[v]=u;
return ;
}
}
return ;
}
int match(int d,int p) {
int res=;
memset(mat,-,sizeof(mat));
for(int i=;i<n*d;i++) // 时间从小到大 一旦找到最大匹配就是最快逃脱时间
if(mat[i]==-) {
memset(vis,,sizeof(vis));
if(dfs(i)) {
res++;
if(res==p) return i/d+;
/// 一旦匹配数等于人数 说明此时所有人都已匹配
}
}
return ;
}
/***/ void solve() {
memset(dis,-,sizeof(dis));
D.clear(), P.clear();
for(int i=;i<n;i++) {
for(int j=;j<m;j++)
if(G[i][j]=='D') {
D.push_back((NODE){i,j});
bfs(i,j,dis[i][j]);// 广搜出所有能到ij门的人的最短时间
} else if(G[i][j]=='.')
P.push_back((NODE){i,j});
} n*=m;
for(int i=;i<E;i++) e[i].clear();
int d=D.size(), p=P.size();
for(int i=;i<d;i++) {
for(int j=;j<p;j++) {
int t=dis[D[i].x][D[i].y][P[j].x][P[j].y];
if(t!=-) { // 说明最快t时间可以逃脱
for(int k=t;k<=n;k++) // 则t以上时间都可逃脱 连边
e[(k-)*d+i].push_back(n*d+j);
}
}
} if(p==) {
printf("0\n"); return;
}
int ans=match(d,p);
if(ans) printf("%d\n",ans);
else printf("impossible\n");
} int main()
{
int t; scanf("%d",&t);
while(t--) {
scanf("%d%d",&n,&m);
for(int i=;i<n;i++)
scanf("%s",G[i]);
solve();
} return ;
}