Problem : 174 - 左手法則

Problem Statistics

Solved Member: 17　　Submission: 91　　User Tried: 21

Statement:

你在玩RPG遊戲，事實上、你走進了一座迷宮。

現在你的視野有限，無法看清迷宮的全貌
當然了你也了解BFS什麼鬼是不切實際的，因為你操控的主角並不會分身術
於是你決定採取一個相對有效的方法：左手法則，來突破這個迷宮

(黑色實心格代表障礙物，綠色圓圈是起點、紅色圓圈是終點，藍色直線代表左手法則的行走路徑)

左手法則的精神就是：「永遠沿著左手邊的牆壁走」
以你一開始進入迷宮的面向為準
如果左手邊有牆壁，那麼沿著牆壁沿伸的方向前進
反之如果左手邊是可以走的空位，那麼往左走

當然，左手法則並不是適用所有的迷宮，像上面這樣就是一個永遠到不了出口的悲劇例子

對給定的迷宮以及起點終點，你只能上下左右走並且不能走障礙物不能超出地圖邊界
請實作一支模擬左手法則的程式，報告是否能到達終點？
如果能的話，左手法則要走幾步？

Input:Output:

每個測試檔僅有一筆測試資料。
第一行有三個正整數n,m,s，以空格隔開，其中n,m表示這張地形圖的長寬、s代表主角一開始的面向(1=左、2=上、3=右、4=下)
緊接著n行，每行有m個字元，描述了迷宮的結構。其中n,m都不超過100
字元'.'代表空格、'A'代表起點、'B'代表終點、'X'代表不可走的障礙物
我們保證地圖恰有一個起點和一個終點
並且起點滿足「以人物起始面向來說」左手邊會是不可走的格子(邊界或障礙)

輸出唯一的一行，包含一個整數
左手法則不可能到達終點，輸出-1。否則輸出左手法則走到終點的步數

Sample Input:Sample Output:

SAMPLE 1
3 5 2
XXXXX
....B
XAXXX

SAMPLE 2
5 5 3
A....
X....
X.B..
X....
XXXXX

SAMPLE 1
6

SAMPLE 2
-1

HINT:

在範例測資一中，路線是「上左右右右右」共6步

Source:

101校內培訓

Problem Setter

lajisongyy_jack1

Testdata:

Test	Time	Memory	Score
0-1	1000ms	65536kb
0-2	1000ms	65536kb
1	1000ms	65536kb	20
2	1000ms	65536kb	20
3	1000ms	65536kb	20
4	1000ms	65536kb	20
5	1000ms	65536kb	20