题意：见挑战230页
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
#define MM(a) memset(a,0,sizeof(a))
typedef long long ll;
typedef unsigned long long ULL;
const int mod = 1000000007;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f;
const int big=50000;
int max(int a,int b) {return a>b?a:b;};
int min(int a,int b) {return a<b?a:b;};
int n,m,x,y;
vector<int> G[100005];
vector<int> dx,dy,px,py;
char field[15][15];
int xx[4]={-1,1,0,0},yy[4]={0,0,1,-1};
int sroad[15][15][15][15],dist[15][15];
int used[30000],match[1000000];
void add_edge(int u,int v)
{
G[u].push_back(v);
G[v].push_back(u);
}
void bfs(int x,int y)
{
memset(dist,-1,sizeof(dist));
dist[x][y]=0;
queue<int> qx,qy;
qx.push(x);
qy.push(y);
while(!qx.empty())
{
int sx=qx.front();
int sy=qy.front();
for(int i=0;i<=3;i++)
{
int tx=sx+xx[i],ty=sy+yy[i];
if(tx>=0&&tx<n&&ty>=0&&ty<m)
if(field[tx][ty]=='.'&&dist[tx][ty]<0)
{
dist[tx][ty]=dist[sx][sy]+1;
sroad[x][y][tx][ty]=dist[tx][ty];
qx.push(tx);
qy.push(ty);
}
}
qx.pop();
qy.pop();
}
}
int dfs(int u)
{
used[u]=1;
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i],w=match[v];
if(w<0||!used[w]&&dfs(w))
{
match[u]=v;
match[v]=u;
return 1;
}
}
return 0;
}
int pipei(int t)
{
int res=0;
for(int i=0;i<dx.size();i++)
{
int u=i+t*dx.size();
if(match[u]<0)
{
memset(used,0,sizeof(used));
if(dfs(u))
res++;
}
}
return res;
}
int num(int t)
{
for(int i=0;i<px.size();i++)
for(int j=0;j<dx.size();j++)
{
int renx=px[i],reny=py[i];
int menx=dx[j],meny=dy[j];
if(sroad[menx][meny][renx][reny]<=t)
add_edge(t*dx.size()+j,(n*m+10)*dx.size()+10+i);
}
return pipei(t);
}
void solve()
{
memset(match,-1,sizeof(match));
int ans=0;
for(int t=0;t<=n*m+3;t++)
{
ans+=num(t);
if(ans>=px.size())
{
cout<<t<<endl;
return;
}
}
cout<<"impossible"<<endl;
}
int main()
{
int cas;
cin>>cas;
while(cas--)
{
scanf("%d %d",&n,&m);
dx.clear();dy.clear();
px.clear();py.clear();
for(int i=0;i<=100005;i++)
G[i].clear();
for(int i=0;i<n;i++)
scanf("%s",field[i]);
memset(sroad,inf,sizeof(sroad));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
if(field[i][j]=='D')
{
dx.push_back(i);
dy.push_back(j);
bfs(i,j);
}
else if(field[i][j]=='.')
{
px.push_back(i);
py.push_back(j);
}
}
solve();
}
return 0;
}
分析：强大的二分匹配（因为一个门一时刻只能通过一个人），这是我的做法，用的是枚举时间
不过看挑战上是直接枚举时间和门组成的二元组的点，每次dfs该点，进行一次匈牙利算法，最后再算出时间
好像程序可以简化一点，不过我的这份代码的效率比较高，排名在270多名，不过开的数组大小很关键，在这个上wa了很多次。
下面是wa代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
#define MM(a) memset(a,0,sizeof(a))
typedef long long ll;
typedef unsigned long long ULL;
const int mod = 1000000007;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f;
const int big=50000;
int max(int a,int b) {return a>b?a:b;};
int min(int a,int b) {return a<b?a:b;};
int n,m,x,y;
vector<int> G[1005];
vector<int> dx,dy,px,py;
char field[15][15];
int xx[4]={-1,1,0,0},yy[4]={0,0,1,-1};
int sroad[15][15][15][15],dist[15][15];
int used[150],match[10000];
void add_edge(int u,int v)
{
G[u].push_back(v);
G[v].push_back(u);
}
void bfs(int x,int y)
{
memset(dist,-1,sizeof(dist));
dist[x][y]=0;
queue<int> qx,qy;
qx.push(x);
qy.push(y);
while(!qx.empty())
{
for(int i=0;i<=3;i++)
{
int tx=qx.front()+xx[i],ty=qy.front()+yy[i];
if(tx>=0&&tx<n&&ty>=0&&ty<m)
if(field[tx][ty]=='.'&&dist[tx][ty]<0)
{
dist[tx][ty]=dist[x][y]+1;
sroad[x][y][tx][ty]=dist[tx][ty];
qx.push(tx);
qy.push(ty);
}
}
qx.pop();
qy.pop();
}
}
int dfs(int u)
{
used[u]=1;
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i],w=match[v];
//printf("%d %d
",v,match[v]);
// printf("match: %d w:%d
",match[v],w);
if(w<0||!used[w]&&dfs(w))
{
match[u]=v;
match[v]=u;
//printf("wwwww
");
return 1;
}
}
return 0;
}
int pipei(int t)
{
int res=0;
for(int i=0;i<dx.size();i++)
{
int u=i+t*dx.size();
//printf("4 match:%d
",match[0]);
if(match[u]<0)
{
memset(used,0,sizeof(used));
if(dfs(u))
res++;
}
}
// printf("res:%d
",res);
return res;
}
int num(int t)
{
for(int i=0;i<px.size();i++)
for(int j=0;j<dx.size();j++)
{
int renx=px[i],reny=py[i];
int menx=dx[j],meny=dy[j];
if(sroad[menx][meny][renx][reny]<=t)
add_edge(t*dx.size()+j,px.size()*dx.size()+10+i);
}
//printf("3 match:%d
",match[0]);
return pipei(t);
}
void solve()
{
memset(match,-1,sizeof(match));
//printf("1 match:%d
",match[0]);
int ans=0;
for(int t=0;t<=n*m+3;t++)
{
ans+=num(t);
//cout<<t<<" "<<num(t)<<endl;
//printf("2 match:%d
",match[0]);
if(ans>=px.size())
{
cout<<t<<endl;
return;
}
}
cout<<"impossible"<<endl;
}
int main()
{
int cas;
cin>>cas;
while(cas--)
{
scanf("%d %d",&n,&m);
dx.clear();dy.clear();
px.clear();py.clear();
for(int i=0;i<=500;i++)
G[i].clear();
for(int i=0;i<n;i++)
scanf("%s",field[i]);
memset(sroad,inf,sizeof(sroad));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
if(field[i][j]=='D')
{
dx.push_back(i);
dy.push_back(j);
bfs(i,j);
}
else if(field[i][j]=='.')
{
px.push_back(i);
py.push_back(j);
}
}
solve();
}
return 0;
}