1466 . 機器人大賽
TopCoder
Tags
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 1
......
....#.
.#.#..
...#..
##....
......
Sample Output 1
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
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 9 |
| 2 | 1 | 9 |
| 3 | 2 | 9 |
| 4 | 3 | 9 |
| 5 | 4 | 9 |
| 6 | 5 | 9 |
| 7 | 6 | 9 |
| 8 | 7 | 9 |
| 9 | 8 | 9 |
| 10 | 9 | 9 |
| 11 | 10 | 10 |