题目描述

发生了火警，所有人员需要紧急疏散！

假设这个房间是一个 $N \times M$ 的矩形区域。每个格子有三个状态：

• 一块空地，可以通行，用 . 表示。
• 一面墙，不可以通行，用 X 表示。
• 一扇门，人们可以从这里撤出房间，用 D 表示。

已知门一定在房间的边界上，并且边界上不会有空地。

最初，每块空地上都有一个人。疏散开始后，每块空地上就没有人数限制了（也就是说每块空地可以同时站无数个人）。

在疏散的时候，每一秒钟每个人都可以向上 / 下 / 左 / 右四个方向移动一格，当然他也可以站着不动。

由于门很窄，每一秒钟只能有一个人移动到门的位置，一旦移动到门的位置，就表示他已经安全撤离了。

现在的问题是：如果希望所有的人安全撤离，最短需要多少时间？或者告知根本不可能。

输入格式

输入文件第一行是由空格隔开的一对正整数 $N,M$（$3 \le N,M \le 20$）。

下面 $N$ 行 $M$ 列是一个 $N\times M$ 的字符矩阵（其中的元素可为字符 .、X 或 D，且字符间无空格），描述这个房间中每个格子的状态。

输出格式

只有一个整数 $K$，表示让所有人安全撤离的最短时间。

如果不可能让所有人安全撤离，那么输出 impossible。

5 5
XXXXX
X...D
XX.XX
X..XX
XXDXX

3

提示

Update on 2015.1.12：新加数据一组。鸣谢：1756500824

对于 C++ 语言，请使用 scanf 读入字符矩阵！