二分图匹配，将各个时刻的门与人相连，跑个二分图就行了
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 4753 | Accepted: 1238 |
Description
Input
Output
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
Source
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<queue> using namespace std; const int maxn = 13; int n,m,T,g[50000],dis[13][13][13][13]; int fx[]={-1,1,0,0},fy[]={0,0,-1,1}; char mp[maxn][maxn]; vector<int> px,py,dx,dy,G[50000]; bool vis[50000]; void adde(int u,int v){ G[u].push_back(v); } bool dfs(int u){ for(int i=0;i<G[u].size();i++){ int v=G[u][i]; if(!vis[v]){ vis[v]=1; if(g[v]==-1||dfs(g[v])) { g[v]=u; return true; } } } return false; } void bfs(int x,int y,int d[13][13]){ queue<int> qx,qy; d[x][y]=0; qx.push(x);qy.push(y); while(!qx.empty()){ int sx=qx.front(),sy=qy.front(); qx.pop();qy.pop(); for(int i=0;i<4;i++){ int ex=fx[i]+sx,ey=fy[i]+sy; if(ex>=0&&ex<n&&ey>=0&&ey<m&&mp[ex][ey]==‘.‘&&d[ex][ey]<0){ d[ex][ey]=d[sx][sy]+1; qx.push(ex);qy.push(ey); } } } } void work(){ px.clear();py.clear(); dx.clear();dy.clear(); memset(dis,-1,sizeof(dis)); for(int i=0;i<n;i++) for(int j=0;j<m;j++){ if(mp[i][j]==‘D‘){ dx.push_back(i);dy.push_back(j); bfs(i,j,dis[i][j]); }else if(mp[i][j]==‘.‘){ px.push_back(i);py.push_back(j); } } int d=dx.size(),p=px.size(); for(int i=0;i<=n*m*d+p;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*m;k++){ adde((k-1)*d+i,n*m*d+j); } } } if(p==0) { puts("0"); return; } memset(g,-1,sizeof(g)); int res=0; for(int i=0;i<n*m*d;i++){ memset(vis,0,sizeof(vis)); if(dfs(i)) if(++res==p) { printf("%d\n",i/d+1); return; } } puts("impossible"); return ; } int main(){ scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%s",mp[i]); work(); } return 0; }
原文：https://www.cnblogs.com/plysc/p/11442353.html
