Description

A fire has broken out, and everyone must evacuate immediately.

Assume the room is an $N \times M$ rectangular area. Each cell is one of the following:

• An empty cell, passable, denoted by ..
• A wall, impassable, denoted by X.
• A door, through which people can leave the room, denoted by D.

Doors are guaranteed to be on the boundary of the room, and there is no empty cell on the boundary.

Initially, each empty cell contains exactly one person. After the evacuation starts, there is no capacity limit per empty cell (that is, any number of people may stand on the same empty cell simultaneously).

During the evacuation, in each second, each person may move one cell up, down, left, or right; they may also stay in place.

Because a door is narrow, in any one second at most one person can move onto a door cell. Once a person moves onto a door cell, they are considered safely evacuated.

Question: if we want everyone to evacuate safely, what is the minimum time required? Or state that it is impossible.

Input Format

The first line contains a pair of space-separated positive integers $N, M$ ($3 \le N, M \le 20$).

The next $N$ lines, each containing $M$ characters, form an $N \times M$ character matrix (each character is one of ./X/D, with no spaces between characters), describing the state of every cell in the room.

Output Format

Output a single integer $K$, the minimum time required for everyone to evacuate safely.

If it is impossible for everyone to evacuate safely, output impossible.

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

3

Hint

Update on 2015.1.12: Added one new set of testdata. Thanks to: 1756500824.

For the C++ language, please use scanf to read the character matrix.

Translated by ChatGPT 5