描述 Description
发生了火警，所有人员需要紧急疏散！假设每个房间是一个 N M 的矩形区域。每个格子如果是’.‘，那么表示这是一块空地；如果是’X’，那么表示这是一面墙，如果是’D’，那么表示这是一扇门，人们可以从这儿撤出房间。已知门一定在房间的边界上，并且边界上不会有空地。最初，每块空地上都有一个人，在疏散的时候，每一秒钟每个人都可以向上下左右四个方向移动一格，当然他也可以站着不动。疏散开始后，每块空地上就没有人数限制了（也就是说每块空地可以同时站无数个人）。但是，由于门很窄，每一秒钟只能有一个人移动到门的位置，一旦移动到门的位置，就表示他已经安全撤离了。现在的问题是：如果希望所有的人安全撤离，最短需要多少时间？或者告知根本不可能。
输入格式 InputFormat
输入文件第一行是由空格隔开的一对正整数 N 与 M，3<=N <=20，3<=M<=20，以下 N 行 M 列描述一个 N M 的矩阵。其中的元素可为字符’.‘、’X’和’D’，且字符间无空格。
输出格式 OutputFormat
只有一个整数 K，表示让所有人安全撤离的最短时间，如果不可能撤离，那么输出’impossible’（不包括引号）。
样例输入 SampleInput
2 1
NY
NY
样例输出 SampleOutput
1
男女分别拆成两点 i,i’,j,j’，i->i’、j’->j 连边容量 k，男 i 女 j 喜欢连接 i->j、不喜欢连接 i’->j’容量均为一。二分答案，源点连接 i 容量二分值，j 连接汇点容量二分值，网络流验证最大流是否是二分值 * n。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int inf = 0x7fffffff / 27.11;
const int maxn = 4 * 55;
const int maxm = maxn * maxn;
int i, j, t, n, m, l, r, k, z, y, x;
struct edge
{
int to, fl, cp, nx;
} e[maxm];
int head[maxn], dis[maxn], used[maxn], cur[maxn];
char ch[maxn];
int num, cnt, sum, mid;
deque <int> q;
inline void ins(int u, int v, int f, int c)
{
e[cnt] = (edge)
{
v, f, c, head[u]
}; head[u] = cnt++;
e[cnt] = (edge)
{
u, 0, 0, head[v]
}; head[v] = cnt++;
}
inline bool bfs(int s, int t, int tim)
{
int i, u, v;
while (!q.empty()) q.pop_front();
dis[s] = 0; used[s] = tim;
q.push_back(s);
while (!q.empty())
{
u = q.front(); q.pop_front();
for (i = head[u]; i != -1; i = e[i].nx)
{
v = e[i].to;
if (used[v] != tim && e[i].fl > 0)
{
used[v] = tim;
dis[v] = dis[u] + 1;
q.push_back(v);
}
}
}
return (used[t] == tim);
}
int dfs(int u, int t, int flow)
{
int i, v, d, k;
if (u == t) return flow;
for (d = flow, i = cur[u]; i != -1; i = e[i].nx)
{
v = e[i].to;
if (dis[v] == dis[u] + 1 && e[i].fl > 0)
{
k = dfs(v, t, min(d, e[i].fl));
e[i].fl -= k; e[i ^ 1].fl += k;
d -= k;
if (d == 0) break;
}
}
return flow - d;
}
inline bool dinic(int s, int t, int lim)
{
int i, ans = 0;
for (i = 0; i < cnt; i++) e[i].fl = (e[i].cp == -1) ? lim : e[i].cp;
while (bfs(s, t, ++num))
{
memcpy(cur, head, sizeof(head));
ans += dfs(s, t, inf);
}
return (ans == lim * n);
}
int main()
{
cnt = num = 0;
memset(head, -1, sizeof(head));
scanf("%d%d", &n, &k);
for (i = 1; i <= n; i++) ins(0, i, 0, -1);
for (i = 1; i <= n; i++) ins(3 * n + i, 4 * n + 1, 0, -1);
for (i = 1; i <= n; i++) ins(i, n + i, k, k), ins(n * 2 + i, n * 3 + i, k, k);
for (i = 1; i <= n; i++)
{
scanf("%s", ch + 1);
for (j = 1; j <= n; j++)
{
if (ch[j] == 'Y') ins(i, 3 * n + j, 1, 1);
else ins(n + i, 2 * n + j, 1, 1);
}
}
l = 0; r = n;
while (l <= r)
{
mid = (l + r) >> 1;
if (dinic(0, 4 * n + 1, mid)) l = mid + 1 ;
else r = mid - 1;
}
printf("%d\n", l - 1);
return 0;
}