11158 - Robot in maze   

Description
小智在火箭隊的地下基地裡遇到了迷宮.

迷宮裡每個 entry 上都有東南西北的方向, 表示要往哪個方向移動到下一個 entry.

那麼給定小智走進迷宮的起始位置, 小智走迷宮會有兩種狀況:

1. 跟著每個 entry 的方向走, 最後走出迷宮.

2. 跟著每個 entry 的方向走, 最後一直在裡面兜圈子.

 

假設小智站在迷宮北方選擇一個 column 走進迷宮,

請問小智最後有沒有走出迷宮?

如果有, 請印出小智走過 N 個 entry.

如果沒有, 請印出小智走過 A 個 entry 後踏入循環路線, 並印出循環路線的總長為 B 個 entry.

 

例如:



Grid1:  N為10

Grid2:  A為3, B為8

 

Hint:

1. 假設讀進來 map 大小為 (row, col), 可以開一個大小為 (row+2, col+2) 的 map, 外面一圈填上 -1, 裡面放讀到的 map. 
    這樣有助於判斷什麼時候走到地圖外 (走到 -1 就是走到原本的地圖外)

2. 可以印出地圖檢查自己每一步有沒有走對, 或檢查讀地圖有沒有讀對

3. 另外開一個 (row+2, col+2) 的 array 裡面都是 0, 當走到某個位置 (x, y) 就在 array 的 (x, y) 位置紀錄目前已經走過幾個 entry.
    這樣有助於判斷循環路線有多長, 因為只要遇到 array 裡不是 0 的地方就表示以下兩點皆成立:
        (1) 這個位置走過了
        (2) 這個位置是循環路線的起點, 把你現在走過的 entry 數減去這個位置的 entry 數能算出循環路線的長度

Input
Grid的row數  Grid的column數  小智從哪個column走進迷宮

迷宮

 

註1: 迷宮大小不超過10x10,  最小為2x2

註2: 每次只會有1筆測資

Output
N

或

A B

 

註: 最後不需加上換行

Sample Input
範例一
3 6 5
NEESWE
WWWESS
SNWWWW

範例二
4 5 1
SESWE
EESNW
NWEEN
EWSEN 
EOF
Sample Output
範例一
10

範例二
3 8 
EOF