轉動迷宮 (APCS 2026-11 中級)

小華有一個彈珠迷宮玩具。迷宮是一張 \(H \times W\) 的地圖，第 \(r\) 列第 \(c\) 欄的格子記為 \((r, c)\)，列由上往下、欄由左往右，都從 \(1\) 開始編號。每一格是牆壁 #、路 .、起點 S 或終點 E，起點和終點各恰好有一個。起點和終點也算是路，彈珠可以從上面經過。地圖的外圍都當成牆壁，彈珠不會滾出地圖。

彈珠一開始放在起點，受重力往下滾：彈珠沿著重力的方向一格一格前進，直到前方是牆壁或地圖外才停下來。接著小華依序做一連串的操作，每個操作都把整個迷宮轉 \(90\) 度：A 是順時針轉，C 是逆時針轉。每轉一次，彈珠就沿著新的重力方向滾動，停下來之後才做下一個操作。

以原本地圖的方向來看，重力一開始朝下，之後依「下 → 右 → 上 → 左」循環：做一次 A，重力換成循環中的下一個方向（朝左的下一個是朝下）；做一次 C，重力換回上一個方向（朝下的上一個是朝左）。

放好彈珠後的第一次滾動稱為第 \(0\) 步，做完第 \(i\) 個操作後的滾動稱為第 \(i\) 步。如果轉動後彈珠的前方立刻就是牆壁或地圖外，彈珠不會移動，但這一步仍然要算。彈珠只要在滾動途中進入終點那一格，就算到達終點，不需要停在終點上。

請算出彈珠在第幾步第一次到達終點。

以範例 1 為例：地圖是 \(5 \times 3\)，起點在 \((1, 1)\)、終點在 \((3, 3)\)，操作依序是 AAC。下圖畫出第 \(0\) 步到第 \(3\) 步，每一張小圖都照原本地圖的方向畫：左上角的數字是步數，旁邊方框裡的字母是這一步之前做的操作，右上角的箭頭是這一步的重力方向；空心圓是這一步開始時彈珠的位置，實心圓是停下來的位置，線是滾過的路徑。第 \(3\) 步彈珠進入終點，這一步的小圖和終點那一格都用粗框標出來。

輸入格式

第一行有兩個正整數 \(H\) 與 \(W\)，代表地圖有 \(H\) 列、\(W\) 欄。

接下來有 \(H\) 行，每行是一個長度為 \(W\) 的字串，由上往下依序是地圖的第 \(1\) 列到第 \(H\) 列；字串的第 \(c\) 個字元是那一列第 \(c\) 欄的格子。

最後一行是一個只由 A 和 C 組成的字串，依序是每一個操作。

限制

• \(1 \le H \le 50\)
• \(1 \le W \le 50\)
• 地圖只由 #、.、S、E 組成，S 和 E 各恰好出現一次。
• 操作字串的長度介於 \(1\) 到 \(1000\) 之間（含），只由 A 和 C 組成。

輸出格式

輸出一個整數，代表彈珠第一次到達終點是第幾步。如果第 \(0\) 步就到達，輸出 \(0\)；如果所有操作都做完，彈珠都沒有到達過終點，輸出 \(-1\)。

評分說明

每一筆測試資料的執行時間限制均為 \(2\) 秒，依正確通過的測試資料筆數給分。

範例輸入 1

5 3
S#.
.#.
..E
...
..#
AAC

範例輸出 1

3

範例解釋 1

第 \(1\) 步往右只滾一格，因為 \((5, 3)\) 是牆壁；第 \(2\) 步往上停在 \((3, 2)\)，因為 \((2, 2)\) 是牆壁。第 \(3\) 步的操作是 C，重力從朝上換回朝右，彈珠往右滾一格就進入終點 \((3, 3)\)，所以答案是 \(3\)。

範例輸入 2

5 5
S....
....#
.#.E.
.....
....#
AACCAACA

範例輸出 2

2

範例解釋 2

• 第 \(0\) 步：重力朝下，\((1, 1) \to (5, 1)\)。
• 第 \(1\) 步：做 A，重力朝右，\((5, 1) \to (5, 4)\)，因為 \((5, 5)\) 是牆壁。
• 第 \(2\) 步：做 A，重力朝上，\((5, 4) \to (1, 4)\)，途中經過終點 \((3, 4)\)。

彈珠沒有停在終點上，但第 \(2\) 步已經進入過終點，所以答案是 \(2\)，後面的 \(6\) 個操作不用再做。

範例輸入 3

4 4
S...
..#.
.#E#
..#.
ACAAC

範例輸出 3

-1

範例解釋 3

終點 \((3, 3)\) 的上、下、左、右四格都是牆壁，不管怎麼轉，彈珠都不可能進入終點，所以輸出 \(-1\)。

題目來源

APCS 2026 年 11 月中級實作題第 3 題。

官方未公布題本，題敘依考生考後回憶整理（豌豆 APCS 提供），細節可能與正式試題有出入。