a068. 廣播訊息迷宮

題目描述

校園廣播室派了一台機器人進入字元迷宮，沿途收集散落的字母，拼成要播出的訊息。機器人一開始站在指定的格子，並面向北、東、南、西其中一個方向。每次它會先處理腳下的格子，再依目前朝向往相鄰格走一步，一直重複。

字母格會把字母加到訊息尾端，並沿原本朝向繼續走；U、D、L、R 是轉向指令，分別把朝向設定成上、下、左、右，不加入訊息，隨後沿新朝向走一步。# 是牆，不能踏入。如果下一步會出界或碰到牆，機器人便停下。

迷宮裡可能繞圈。處理一格時，若它的座標與處理該格指令後的朝向和先前處理過的狀態相同，就在這次收集字母之前停止，避免讓訊息無限增長。最後輸出依序收到的字母；若從頭到尾沒收到任何字母，就輸出 -。起點保證不是牆。

輸入格式

第一行 R C，接著 R 行方格；最後一行為起點 r c d，其中 d 為 N、E、S、W。起點不是牆，座標從 1 開始。

限制

• 1 ≤ R, C ≤ 30
• 字母格可用 A 至 Z，但不包含保留作方向指令的 U、D、L、R；其餘格子只含方向指令或 #

輸出格式

輸出一行，依序收到的字母；若沒有收到字母則輸出 -。

範例1

範例輸入：

2 3
AB#
CXE
1 1 E

範例輸出：

AB

從左上角朝東出發，先收集 A、B；下一步面前是牆，機器人停下。

範例2

範例輸入：

1 2
RL
1 1 E

範例輸出：

-

機器人走回相同位置及朝向時停止。