TopCoder

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Description

還記得機器人組裝大賽(TIOJ 1445)嗎?

上次在你的程式協助之下,你成功的拿下了機器人組裝大賽的冠軍!

這次,你帶著上次組裝好的機器人,參加了一場更盛大的機器人大賽。

這次的主題是一個很經典的題目:「走迷宮」。

在你面前的是一個 m 乘 n 的迷宮,其中有許多單位大小的正方形障礙物。

因為你的機器人是兩單位乘以一單位大小的,外觀如下方圖所示,情況就變的有些複雜。

而你的目標是要控制機器人從起點開始走到終點。

起點位置為左上角(1,1)和(2,1),終點為右下角(m-1,n)和(m,n),機器人剛開始是面朝下方,而到終點的時候,也必須要是面朝下方,並且剛好停在終點兩格才算通過。

你可以對機器人下的指令有兩種:

第一種是 Rotate a b,其中 a 為 0 或 1 ,分別表示要它前段固定或後端固定。
b 為 -90 或 90,分別表示要它順時鐘旋轉90度或逆時鐘旋轉90度( 以固定的這端來看 )。
注意:旋轉時會經過的格子不能有障礙物。

第二種是 Go ,表示要它朝面向的方向前進一單位。

請問你至少要下多少個指令,才能讓機器人走到終點呢?

Input Format

本題只有一組測試資料:

第一行有兩個數 m, n,分別代表迷宮的長和寬。( 2 <= m <= 100, 1 <= n <= 100 )

接下來有 m 行,每行有 n 個字元,表示這張迷宮。

其中'.'為空地,'#'為障礙物。

我們保證起點和終點都不會有障礙物。

Output Format

請輸出一個正整數 t ,代表最少需要多少個指令。
如果無法通過這個迷宮,請輸出"No Way!"。( 不含雙引號 )

Sample Input

6 6
......
....#.
.#.#..
...#..
##....
......

Sample Output

13

Hints

範例測資的圖:

一種可以通過這個迷宮的指令:
Rotate 1 -90
Go
Go
Rotate 1 90
Go
Go
Go
Go
Rotate 1 -90
Go
Go
Rotate 0 90
Go

Problem Source

原TIOJ1466 / 建中校內培訓第四次模擬考試。
Problem Setter:hallogameboy、peter50216

Subtasks

For Testdata: 0 ~ 0, Score: 9
For Testdata: 1 ~ 1, Score: 9
For Testdata: 2 ~ 2, Score: 9
For Testdata: 3 ~ 3, Score: 9
For Testdata: 4 ~ 4, Score: 9
For Testdata: 5 ~ 5, Score: 9
For Testdata: 6 ~ 6, Score: 9
For Testdata: 7 ~ 7, Score: 9
For Testdata: 8 ~ 8, Score: 9
For Testdata: 9 ~ 9, Score: 9
For Testdata: 10 ~ 10, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
3 1000 65536 262144
4 1000 65536 262144
5 1000 65536 262144
6 1000 65536 262144
7 1000 65536 262144
8 1000 65536 262144
9 1000 65536 262144
10 1000 65536 262144