在一次的暴風雨後,海明威的船被困在了滿佈暗礁的海域中。
他的船很特別,一定會沿著某個水平或垂直的軸對稱,並且船體沿著這條軸從船首到船尾其寬度先是遞增然後再遞減。
海恩威想要趕快回到宿舍打鬥塔,所以他希望能找到一條不觸礁的航線離開這片危險海域。
已知暗礁在地圖上的位置,請問在不碰到任何暗礁的情況下最快只要航行「幾步」就可以讓整艘船都遠離危險海域呢?
注意因為暗礁的關係,船的「每一步」只能往前後左右四個方向前進一個單位長。
並且遠離危險海域的意思就是整艘船都要移動到目前的地圖外。
輸入的第一列會有一個正整數 n (3<=n<=2000),接下來會有一張 n*n 大小的地圖。
地圖上的每一格都會以'.'代表安全海域、'X'代表暗礁、'r'代表海明威的船。
請輸出至少要幾步才能讓整艘船離開危險海域,如果無論如何都沒有辦法離開危險海域的話,請輸出 "impossible"(不含引號)。
原TIOJ1523 / 2009宵夜盃練習賽II。POI 2007 Stage I。
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 |