题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1189
数据生成器：http://paste.ubuntu.com/23173568/
这题还是很好想的，要么二分时间，要么时间上暴力
然而HZWER的做法是错误的，门那里肯定需要按时间拆点
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 500000;
const int M = 2000000;
const int L = 30;
const int INF = 10000000;
int n,m,mat[L][L],S,T,vout,dis[N],cur[N];
int nxt[M],to[M],flow[M],head[N],nod_cnt;
char pat[L]; vector<int> num[N],dor; queue<int> que;
#define id(x,y) ((x)+((y)-1)*n)
inline void Add_Edge(int u, int v, int f){
static int TT = 1;
to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f;
to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0;
}
inline bool BFS(){
memset(dis,-1,sizeof(dis));
dis[S] = 0; que.push(S);
while (!que.empty()) {
int w = que.front(); que.pop();
for (int i=head[w];i;i=nxt[i]) if (flow[i] && !~dis[to[i]])
dis[to[i]] = dis[w] + 1, que.push(to[i]);
} return ~dis[T];
}
int DFS(int w, int f) {
if (w == T) return f;
else { int ret = 0;
for (int &i=cur[w];i;i=nxt[i]) if (flow[i] && dis[to[i]] == dis[w] + 1) {
int tmp = DFS(to[i], min(f, flow[i]));
ret += tmp; f -= tmp; flow[i] -= tmp; flow[i^1] += tmp;
if (!f) break;
} return ret;
}
}
inline int Dinic(){
int ret = 0; while (BFS()) {
memcpy(cur,head,sizeof(head));
ret += DFS(S,INF);
} return ret;
}
inline void search(int s){
memset(dis,-1,sizeof(dis));
que.push(s); dis[s] = 0;
while (!que.empty()) {
int w = que.front(); que.pop();
int x=w, y=0; while ((y+1)*n < w) y++; x -= y*n; y++;
if (mat[x][y] == 1) Add_Edge(w,num[s][dis[w]],1);
if (x - 1 >= 1 && !~dis[id(x-1,y)] && mat[x-1][y] == 1) que.push(id(x-1,y)), dis[id(x-1,y)] = dis[w] + 1;
if (x + 1 <= n && !~dis[id(x+1,y)] && mat[x+1][y] == 1) que.push(id(x+1,y)), dis[id(x+1,y)] = dis[w] + 1;
if (y - 1 >= 1 && !~dis[id(x,y-1)] && mat[x][y-1] == 1) que.push(id(x,y-1)), dis[id(x,y-1)] = dis[w] + 1;
if (y + 1 <= m && !~dis[id(x,y+1)] && mat[x][y+1] == 1) que.push(id(x,y+1)), dis[id(x,y+1)] = dis[w] + 1;
}
}
int main(){
cin>>m>>n; S = 0; T = N-1; nod_cnt = n*m;
for (int j=1;j<=m;j++) {
scanf("%s",pat+1);
for (int i=1;i<=n;i++)
if (pat[i] == 'X') mat[i][j] = 2;
else if (pat[i] == '.') mat[i][j] = 1, vout++, Add_Edge(S,id(i,j),1);
else dor.push_back(id(i,j));
}
for (int i=0,lim=dor.size();i<lim;i++) for (int k=1;k<=n*m;k++) num[dor[i]].push_back(++nod_cnt);
for (int i=0,lim=dor.size();i<lim;i++) search(dor[i]);
for (int k=0,ret=0;k<n*m;k++) {
ret += Dinic();
if (ret == vout) printf("%d\n",k), exit(0);
for (int i=0,lim=dor.size();i<lim;i++)
Add_Edge(num[dor[i]][k],num[dor[i]][k+1],INF),
Add_Edge(num[dor[i]][k+1],T,1);
} puts("impossible");
return 0;
}
