轉動迷宮 題解｜APCS 2026 年 11 月中級 第 3 題
簡潔題意
\(H \times W\) 的地圖上，每一格是牆壁 #、路 .、起點 S 或終點 E（起點、終點也是路），地圖外圍當成牆壁。彈珠放在起點，以原地圖來看重力一開始朝下；每一步彈珠都沿重力方向一格一格滾，直到前方是牆壁或地圖外才停。放好後的第一次滾動是第 \(0\) 步；接著依序做操作字串的每一個字元：A 讓重力換成「下 → 右 → 上 → 左」循環的下一個方向，C 換回上一個，做完第 \(i\) 個操作後的滾動是第 \(i\) 步（彈珠沒動也算一步）。滾動途中進入終點那一格就算到達，輸出第一次到達是第幾步；所有操作做完都沒到達，輸出 \(-1\)（\(1 \le H, W \le 50\)，操作字串長度 \(1\)～\(1000\)）。
依正確通過的測試資料筆數給分，其中：
- 子題組 1（\(60\) 分）：操作字串只包含
A。 - 子題組 2（\(40\) 分）：無額外限制。
先拿下子題組 1（60 分）：只有 A，第 \(i\) 步的方向就是 i % 4
地圖用 string 陣列一列一列讀進來，照 \(H\) 的上限開 string grid[MAX_H]。程式裡列、欄都從 \(0\) 開始編號，題目說的 \((r, c)\) 就是 grid[r - 1][c - 1]。先掃一遍找到 S，彈珠從那裡出發。
方向打成表，照題目的循環排：\(0\) 下、\(1\) 右、\(2\) 上、\(3\) 左。常見的方向表是上、右、下、左；這題照題目的順序排，換到下一個方向才剛好是編號加一。子題組 1 只有 A，重力每一步都換到下一個：第 \(0\) 步朝下、第 \(1\) 步朝右、第 \(2\) 步朝上、第 \(3\) 步朝左、第 \(4\) 步又朝下……所以第 \(i\) 步的方向就是 i % 4，操作字元一個都不用看。
每一步的滾動就是「沿一個方向一直走」：先算前方那一格，出界或是牆就停，否則踏上去。出界要先判，確定在地圖裡才能讀 grid[nr][nc]。題目要的是進入終點，不必停在上面，所以每踏上一格就檢查是不是 E——範例 2 的第 \(2\) 步就是滾過終點、停在 \((1, 4)\)。
操作有 \(n\) 個，滾動卻有 \(n + 1\) 次：放好彈珠的第 \(0\) 步也要滾、也要檢查。所以 step 從 \(0\) 跑到 \(n\)；第一次踏進終點就印出 step，直接 return 0 結束——寫 break 只會跳出滾動那一層迴圈。全部跑完都沒到，印 \(-1\)。
#include <bits/stdc++.h>
using namespace std;
// 方向照題目的循環編號：0 下、1 右、2 上、3 左
const int dr[4] = {1, 0, -1, 0}; // 列的變化
const int dc[4] = {0, 1, 0, -1}; // 欄的變化
const int MAX_H = 50;
string grid[MAX_H]; // 地圖：一列一條字串
int main() {
int h, w;
cin >> h >> w;
for (int i = 0; i < h; i++) cin >> grid[i];
string ops;
cin >> ops;
int n = ops.size();
int r = 0, c = 0; // 彈珠的位置：從起點出發
for (int i = 0; i < h; i++)
for (int j = 0; j < w; j++)
if (grid[i][j] == 'S') {
r = i;
c = j;
}
for (int step = 0; step <= n; step++) { // 第 0 步到第 n 步，一共滾 n + 1 次
int d = step % 4; // 子題組 1 只有 A：第 step 步朝第 step % 4 個方向
while (true) { // 沿重力方向一格一格滾
int nr = r + dr[d], nc = c + dc[d]; // 前方那一格
if (nr < 0 || nr >= h || nc < 0 || nc >= w) break; // 前方是地圖外：停
if (grid[nr][nc] == '#') break; // 前方是牆：停
r = nr;
c = nc;
if (grid[r][c] == 'E') { // 每踏上一格就檢查
cout << step << '\n';
return 0;
}
}
}
cout << -1 << '\n';
return 0;
}
這份程式交上去，範例 1 會 WA：第 \(3\) 個操作是 C，它照樣當成 A 往左滾，印 -1。這是正常的，逐筆給分之下子題組 1 的 \(60\) 分穩穩到手。
從 60 分到 100 分：A 是加一，C 是加三
有了 C，第 \(i\) 步的方向就不能再用 i % 4 算，改用變數 d 記住現在的方向，一開始是 \(0\)（下）。第 step 步滾之前，先做第 step 個操作，也就是 ops[step - 1]（字串從 \(0\) 開始編號；第 \(0\) 步沒有操作）：
A換到下一個方向：d = (d + 1) % 4，左（\(3\)）的下一個回到下（\(0\)）。C換回上一個方向：d = (d + 3) % 4。四個方向繞成一圈，往回走一格就是往前走三格。
圖 1 把四個方向照原地圖的方位擺成一圈。迷宮順時針轉，以原地圖來看重力是往反方向轉，所以圖上 A 是逆時針繞。
為什麼不寫 d = (d - 1) % 4？C++ 的 % 算出來的餘數，正負號跟被除數一樣（語法書 2.6）：重力朝下時 d 是 \(0\)，(0 - 1) % 4 得到 \(-1\)，不是 \(3\)。方向表沒有第 \(-1\) 格，dr[-1] 會讀到陣列外面，彈珠怎麼動就說不準了。加 \(3\) 就不會碰到負數，這也是左轉寫成 (d + 3) % 4 的原因。三個範例剛好都沒有「重力朝下時做 C」，這個錯範例抓不到。
#include <bits/stdc++.h>
using namespace std;
// 方向照題目的循環編號：0 下、1 右、2 上、3 左
const int dr[4] = {1, 0, -1, 0}; // 列的變化
const int dc[4] = {0, 1, 0, -1}; // 欄的變化
const int MAX_H = 50;
string grid[MAX_H]; // 地圖：一列一條字串
int main() {
int h, w;
cin >> h >> w;
for (int i = 0; i < h; i++) cin >> grid[i];
string ops;
cin >> ops;
int n = ops.size();
int r = 0, c = 0; // 彈珠的位置：從起點出發
for (int i = 0; i < h; i++)
for (int j = 0; j < w; j++)
if (grid[i][j] == 'S') {
r = i;
c = j;
}
int d = 0; // 重力一開始朝下
for (int step = 0; step <= n; step++) { // 第 0 步到第 n 步，一共滾 n + 1 次
if (step > 0) { // 第 step 步要先做第 step 個操作
if (ops[step - 1] == 'A') d = (d + 1) % 4; // A：下一個方向
else d = (d + 3) % 4; // C：上一個方向（往回一格＝往前三格）
}
while (true) { // 沿重力方向一格一格滾
int nr = r + dr[d], nc = c + dc[d]; // 前方那一格
if (nr < 0 || nr >= h || nc < 0 || nc >= w) break; // 前方是地圖外：停
if (grid[nr][nc] == '#') break; // 前方是牆：停
r = nr;
c = nc;
if (grid[r][c] == 'E') { // 每踏上一格就檢查
cout << step << '\n';
return 0;
}
}
}
cout << -1 << '\n';
return 0;
}
跟子題版比，換掉的只有一件事：方向不再用 step % 4 算，改成用 d 記著、每一步先照操作轉。滾動和檢查一個字都沒改。地圖最大 \(50 \times 50\)，每一步最多滾 \(49\) 格，第 \(0\) 步到第 \(1000\) 步加起來不到 \(5 \times 10^4\) 格，一下就跑完。
測過再交：範例裡的重力從來沒朝左
三個範例分別考了停在終點上（範例 1）、滾過終點（範例 2）、到不了終點（範例 3），但重力只朝過下、右、上——從來沒朝左，所以也沒有「重力朝下時做 C」、沒有「左的下一個回到下」。答案沒有 \(0\)；「轉了沒動也算一步」「起點也是路」「要輸出第一次到達」這三件事寫錯了，三個範例的答案也都不會變。地圖越小越好算，自己造：
| 輸入 | 正確輸出 | 這一筆在測什麼 |
|---|---|---|
1 2 ／ ES ／ C |
1 |
重力朝下時做 C：換成朝左，往左滾一格就進終點 |
2 1 ／ S ／ E ／ A |
0 |
起點正下方就是終點：第 \(0\) 步就滾進去、停在上面 |
2 3 ／ .S. ／ E#. ／ AAAA |
4 |
第 \(0\)、\(2\) 步彈珠不動，但都要算；第 \(3\) 步往左滾過起點；第 \(4\) 步轉滿一圈、重力又朝下才進終點 |
1 3 ／ S.E ／ AAAAA |
1 |
第 \(1\) 步就滾進終點，第 \(5\) 步又經過一次：要輸出第一次 |
四筆都親眼看過正確，這題就穩了。
常犯錯誤
- 只檢查停下的那一格：滾過終點不算到達，範例 2 印
-1。 - 沒有第 0 步（放好彈珠就直接做第 1 個操作）：範例 1、2 都印
-1。 C寫成d = (d - 1) % 4：範例全過，自測表第 1 列抓得到。A寫成d = d + 1、沒有取餘：範例全過（範例的d最大只到 \(2\)），自測表第 3 列抓得到。- 起點當成牆（前方是
.或E才走）：範例全過，自測表第 3 列印-1。 - 到達終點只寫
break、最後才印答案：外層照跑，答案被後來再經過終點的步數蓋掉——範例全過，自測表第 4 列印5。