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

3
21
impossible

题目大意：有一个n*m的格子房间，某些格子是柱子X，则不能站人，而 . 表示此处是空地，可以站无限多的人。在周围的格子上有一些门D。现在这个房子着火了，每个空地 . 上有一个人，然后他们每秒可以向上下左右走一格或者原地不动。一个门一秒内只能通过一个人。问全部人逃跑至少需要多少时间，如果无法逃出则输出impossible。

分析：首先需要了解时间动态流模型。如果不明白请参照经典例题：

SGU438 The Glorious Karlutka River

http://blog.csdn.net/maxichu/article/details/45219567

我看了看《挑战》上关于此题的解法，是一种二分图匹配的算法，不是很明白。所以还是用的动态流模型。一开始先让超级源点连接每一个格子，负载为1，表示有一个人。注意每个格子需要拆点，负载为INF，因为格子上可以站无限多的人（其实本不需要拆点，为了配合门我懒得分了于是就都拆了。。。反正空间充足）。然后我们遍历时间，从1开始进行直到150（因为最坏的情况也不会超过144s，150是写着方便）。我们关注现在进行到时刻 t ，在时刻 t 的层次残余流量图中。对于每个空地( i , j ) t，首先将 t 时刻的状态拆点。然后这个空地的周围四个格子上一秒的状态一定可以转换过来，那么就连边。

                                                 int nx = i + mox[k], ny = j + moy[k];
if(nx >= 1 && nx <= n&&ny >= 1 && ny <= m&&map[nx][ny] != ‘X‘)
addedge( (t - 1) * 300 + (nx - 1) * 12 + ny + 150, t * 300 + (i - 1) * 12 + j, INF );

同样对于时刻 t 的门( i , j ) t，首先连接它与超级汇点des。然后这个门周围的四个格子的上一秒的状态也可以转换过来，那么就连边。

int nx = i + mox[k], ny = j + moy[k];
if(nx >= 1 && nx <= n&&ny >= 1 && ny <= m&&map[nx][ny] != ‘X‘)
addedge( (t - 1) * 300 + (nx-1) * 12 + ny + 150, t * 300 + (i - 1) * 12 + j, INF );

其实门与空地状态更新是一样的，主要区别在于拆不拆点。（其实我写的时候发现好像不拆点也行，但是也不想改了，囧）。这一秒连边结束后跑最大流，看看最大流的总和是否已经超过了人数peo，超过就退出。最后根据 t 输出答案即可。

上代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstdio>
using namespace std;

const int MAXN = 65010;
const int MAXM = 990000;
const int INF = 0x3f3f3f3f;

struct Edge
{
	int from, to, cap, next;
};

int mox[5] = { 0, -1, 1, 0, 0 };
int moy[5] = { 0, 0, 0, -1, 1 };
Edge edge[MAXM];
int level[MAXN];
char map[15][15];
int head[MAXN];
int src, des, cnt;

void addedge(int from,int to,int cap)
{
	edge[cnt].from = from;
	edge[cnt].to = to;
	edge[cnt].cap = cap;
	edge[cnt].next = head[from];
	head[from] = cnt++;

	swap( from, to );

	edge[cnt].from = from;
	edge[cnt].to = to;
	edge[cnt].cap = 0;
	edge[cnt].next = head[from];
	head[from] = cnt++;
}

int bfs()
{
	memset( level, -1, sizeof level );
	queue<int> q;
	while(!q.empty())
		q.pop();

	level[src] = 0;
	q.push( src );

	while(!q.empty())
	{
		int u = q.front();
		q.pop();

		for(int i = head[u]; i != -1; i = edge[i].next)
		{
			int v = edge[i].to;
			if(edge[i].cap&&level[v] == -1)
			{
				level[v] = level[u] + 1;
				q.push( v );
			}
		}
	}
	return level[des] != -1;
}

int dfs( int u, int f )
{
	if(u == des)
		return f;
	int tem;
	for(int i = head[u]; i != -1; i = edge[i].next)
	{
		int v = edge[i].to;
		if(edge[i].cap > 0 && level[v] == level[u] + 1)
		{
			tem = dfs( v, min( f, edge[i].cap ) );
			if(tem > 0)
			{
				edge[i].cap -= tem;
				edge[i^1].cap += tem;
				return tem;
			}
		}
	}
	level[u] = -1;
		return 0;
}

int Dinic()
{
	int ans = 0, tem;
	while(bfs())
	{
		while((tem = dfs( src, INF ) > 0))
		{
			ans += tem;
		}
	}
	return ans;
}

int main()
{
	int kase;
	cin >> kase;
	int n, m,peo;
	src = 0; des = 65005;
	while(kase--)
	{
		memset( head, -1, sizeof head );
		cnt = 0;
		peo = 0;
		cin >> n >> m;
		for(int i = 1; i <= n; i++)
		{
			for(int j = 1; j <= m; j++)
			{
				cin >> map[i][j];
			}
		}

		for(int i = 1; i <= n; i++)
		{
			for(int j = 1; j <= m; j++)
			{
				if(map[i][j] == '.')
				{
					peo++;
					addedge( src, (i-1) * 12 + j, 1 );
					addedge( (i - 1) * 12 + j, (i - 1) * 12 + j + 150, INF );
				}
			}
		}
		int ans = 0;
		int t;
		for( t = 1; t <= 150; t++) //枚举时间 多次增广
		{

			for(int i = 1; i <= n; i++)
			{
				for(int j = 1; j <= m; j++)
				{
					if(map[i][j] == '.')
					{
						addedge( t * 300 + (i - 1) * 12 + j, t * 300 + (i - 1) * 12 + j + 150, INF );
						for(int k = 0; k <= 4; k++)
						{
							int nx = i + mox[k], ny = j + moy[k];
							if(nx >= 1 && nx <= n&&ny >= 1 && ny <= m&&map[nx][ny] != 'X')
								addedge( (t - 1) * 300 + (nx - 1) * 12 + ny + 150, t * 300 + (i - 1) * 12 + j, INF );
						}
					}
					if(map[i][j] == 'D')
					{
						addedge( t * 300 + (i - 1) * 12 + j, des, 1 );
						for(int k = 0; k <= 4; k++)
						{
							int nx = i + mox[k], ny = j + moy[k];
							if(nx >= 1 && nx <= n&&ny >= 1 && ny <= m&&map[nx][ny] != 'X')
								addedge( (t - 1) * 300 + (nx-1) * 12 + ny + 150, t * 300 + (i - 1) * 12 + j, INF );
						}
					}
				}
			}
			ans += Dinic();
			if(ans >= peo) break;

		}
		if(t > 150) cout << "impossible" << endl;
		else	cout << t << endl;
	}

	return 0;
}