TopCoder

Thumb coevr
Kevin_Zhang
\(I\ want\ to\ be\ better!\ But\ how.....\)

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

9.7% (3/31)

Description

在一次的暴風雨後,海明威的船被困在了滿佈暗礁的海域中。

他的船很特別,一定會沿著某個水平或垂直的軸對稱,並且船體沿著這條軸從船首到船尾其寬度先是遞增然後再遞減。

海恩威想要趕快回到宿舍打鬥塔,所以他希望能找到一條不觸礁的航線離開這片危險海域。

已知暗礁在地圖上的位置,請問在不碰到任何暗礁的情況下最快只要航行「幾步」就可以讓整艘船都遠離危險海域呢?
注意因為暗礁的關係,船的「每一步」只能往前後左右四個方向前進一個單位長。
並且遠離危險海域的意思就是整艘船都要移動到目前的地圖外。

Input Format

輸入的第一列會有一個正整數 n (3<=n<=2000),接下來會有一張 n*n 大小的地圖。
地圖上的每一格都會以'.'代表安全海域、'X'代表暗礁、'r'代表海明威的船。

Output Format

請輸出至少要幾步才能讓整艘船離開危險海域,如果無論如何都沒有辦法離開危險海域的話,請輸出 "impossible"(不含引號)。

Sample Input

10
..........
..........
..r.......
.rrrX.....
rrrrr.....
.rrr......
X.r.......
.Xr.......
..........
..........

Sample Output

10

Hints

Problem Source

原TIOJ1523 / 2009宵夜盃練習賽II。POI 2007 Stage I。

Subtasks

No. Testdata Range Score
1 0 4
2 1 4
3 2 4
4 3 4
5 4 4
6 5 4
7 6 4
8 7 4
9 8 4
10 9 4
11 10 4
12 11 4
13 12 4
14 13 4
15 14 4
16 15 4
17 16 4
18 17 4
19 18 4
20 19 4
21 20 4
22 21 4
23 22 12

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 15000 262144 262144 1
1 15000 262144 262144 2
2 15000 262144 262144 3
3 15000 262144 262144 4
4 15000 262144 262144 5
5 15000 262144 262144 6
6 15000 262144 262144 7
7 15000 262144 262144 8
8 15000 262144 262144 9
9 15000 262144 262144 10
10 15000 262144 262144 11
11 15000 262144 262144 12
12 15000 262144 262144 13
13 15000 262144 262144 14
14 15000 262144 262144 15
15 15000 262144 262144 16
16 15000 262144 262144 17
17 15000 262144 262144 18
18 15000 262144 262144 19
19 15000 262144 262144 20
20 15000 262144 262144 21
21 15000 262144 262144 22
22 15000 262144 262144 23