a076. 無人機巡邏

題目描述

一台無人機在 R × C 的地圖上巡邏。. 是可通行格，# 是不能進入的障礙物；無人機一開始站在可通行格上，面向北 N、東 E、南 S、西 W 其中一個方向。所有座標都從 0 開始，向下是行號增加、向右是列號增加。

控制器依序送出指令：L 代表原地向左轉 90 度，R 代表原地向右轉 90 度，F k 代表嘗試朝目前方向前進 k 格，每次只跨一格。若下一格是障礙物或地圖外，就立刻結束這道 F 指令，不會穿越障礙物，也不會執行尚未走完的步數；後面的指令仍照常執行。

起點算造訪過。每成功踏入一格便視為造訪該格；同一格就算反覆經過很多次，在『不同造訪格數』中也只算一次。請在全部指令執行完後，輸出無人機的位置、面向與不同造訪格數。

規則圖解

以目前位置 (r, c) 為中心，四個方向的下一格分別是：

              N: (r-1, c)
                   ↑
W: (r, c-1) ← (r, c) → E: (r, c+1)
                   ↓
              S: (r+1, c)

指令	對位置的影響	對面向的影響
L	不移動	逆時針轉 90 度，例如 N → W
R	不移動	順時針轉 90 度，例如 N → E
F k	最多前進 k 格；遇到無法進入的下一格就停	不變

範例一的執行過程（造訪格數包含起點）：

已執行指令	目前座標	面向	不同造訪格數
尚未執行	(2, 1)	N	1
F 2	(2, 1)	N	1
R	(2, 1)	E	1
F 2	(2, 3)	E	3
L	(2, 3)	N	3
F 3	(0, 3)	N	5
L	(0, 3)	W	5
F 3	(0, 0)	W	8

第一次 F 2 的第一步就會撞上 (1, 1) 的障礙物，因此這道指令一格也沒走。指令停止不等於結束整段巡邏。

輸入格式

依序讀入：

1. 第一行：R C，地圖行數與列數。
2. 接下來 R 行：每行恰好 C 個連續字元，只有 .（空地）或 #（障礙），字元之間沒有空白。
3. 下一行：r c dir，起點行號、列號與初始面向；dir 是 N、E、S、W 之一。
4. 下一行：Q，指令數量。
5. 接下來 Q 行：每行是一道 L、R 或 F k 指令，必須按輸入順序執行。

座標從 0 起算；轉向指令沒有額外參數。

限制

• 1 ≤ R, C ≤ 100；1 ≤ Q ≤ 1000；1 ≤ k ≤ 100
• 起點保證在地圖內，且是 .

輸出格式

輸出一行：最後的行 最後的列 最後的方向 不同造訪格數。方向請使用大寫 N、E、S 或 W；同一格走訪多次只計一次，起點一定計入。

範例1

範例輸入：

3 4
....
.#..
....
2 1 N
7
F 2
R
F 2
L
F 3
L
F 3

範例輸出：

0 0 W 8

第一道指令往北的下一格就是障礙物，因此無人機先留在起點。

範例2

範例輸入：

1 1
.
0 0 W
4
F 100
L
F 1
R

範例輸出：

0 0 W 1

轉向會改變面向，但單格地圖無法前進，造訪格數仍為 1。