Editorial for 路徑偵測 (APCS 2023-06 初級)
簡潔題意
從 \((0, 0)\) 出發，依序走過 \(n\) 個座標點，每一步只往東西南北其中一個方向直走；題目保證第一個點在 X 軸正向（一開始向東）。統計整條路徑上左轉、右轉、迴轉各幾次，依序輸出（\(1 \le n \le 100\)；直行不算轉彎）。
依正確通過的測試資料筆數給分，其中：
- 子題組 1（\(60\) 分）：\(n = 2\)。
- 子題組 2（\(40\) 分）：\(n \le 100\)。
先拿下子題組 1（\(60\) 分）：只有一個轉彎要判斷
\(n = 2\) 時路徑只有兩段：\((0,0) \to\) 第一個點（題目保證向東）、第一個點 \(\to\) 第二個點。轉彎只發生在第一個點，判斷第二段往哪走就結束了，連迴圈都不用——只用到語法書上冊第三單元為止的語法。
第二段的方向，拿第二個點跟第一個點比（注意：是跟第一個點比，不是跟原點比）：
- \(y\) 變大 → 轉向北。原本面朝東，北在左手邊 → 左轉。
- \(y\) 變小 → 轉向南 → 右轉。
- \(x\) 變小 → 掉頭向西 → 迴轉。
- \(x\) 變大 → 繼續向東 → 直行，什麼都不用數。
#include <iostream>
using namespace std;
int main() {
int n; // 子題組 1 保證 n = 2
int x1, y1, x2, y2;
cin >> n;
cin >> x1 >> y1 >> x2 >> y2;
// 第一段保證向東，所以只要判斷第二段轉去了哪裡
if (y2 > y1) {
cout << 1 << " " << 0 << " " << 0 << endl; // 轉向北＝左轉
} else if (y2 < y1) {
cout << 0 << " " << 1 << " " << 0 << endl; // 轉向南＝右轉
} else if (x2 < x1) {
cout << 0 << " " << 0 << " " << 1 << endl; // 掉頭向西＝迴轉
} else {
cout << 0 << " " << 0 << " " << 0 << endl; // 繼續向東＝直行
}
return 0;
}
範例 2 的 \(n = 9\)，這支程式讀不完，答案會是錯的——這是正常的：APCS 逐筆給分，這一版穩穩拿下子題組 1 的 \(60\) 分。
從 \(60\) 分到 \(100\) 分：把方向編成數字，轉彎就變成減法
\(n\) 變大之後，每個點都要做一樣的判斷：「上一段朝哪、這一段朝哪、所以轉了什麼」。方向只有四種，把它們編成 \(0\)、\(1\)、\(2\)、\(3\)，而且故意按逆時針排：東 \(0\)、北 \(1\)、西 \(2\)、南 \(3\)。
這個編號的好處是：左轉一次，編號剛好 \(+1\)（東 \(\to\) 北 \(\to\) 西 \(\to\) 南 \(\to\) 東）。所以「這一段編號 \(-\) 上一段編號」就直接告訴你轉了幾個逆時針 \(90\) 度：
| 編號差 | 意義 |
|---|---|
| \(0\) | 直行（不計） |
| \(+1\) | 左轉 |
| \(+2\) | 迴轉 |
| \(+3\)（也就是 \(-1\)） | 右轉 |
差是負的怎麼辦？繞了一圈回來而已——先 \(+4\) 再取餘數 % 4，就把 \(-1\) 折回 \(3\)、\(-2\) 折回 \(2\)。（先加再取餘是必要的：C++ 對負數取餘會給出負的結果，\(-1 \% 4\) 是 \(-1\) 不是 \(3\)。）
每一段的方向跟上一個點比座標就知道；整條路徑用 px、py 記住上一個點、prevDir 記住上一段方向，一路滑過去。新增的語法只有第四單元的單層 for——不需要陣列。
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int px, py; // 上一個點
cin >> px >> py; // 第一個點：題目保證從 (0,0) 走到這裡是向東
int prevDir = 0; // 上一段方向：0=東 1=北 2=西 3=南（逆時針編號）
int L = 0, R = 0, U = 0;
for (int i = 2; i <= n; i++) {
int x, y;
cin >> x >> y;
int dir; // 這一段的方向：跟上一個點比就知道
if (x > px) {
dir = 0; // 東
} else if (y > py) {
dir = 1; // 北
} else if (x < px) {
dir = 2; // 西
} else {
dir = 3; // 南
}
int turn = (dir - prevDir + 4) % 4; // 逆時針轉了幾個 90 度
if (turn == 1) L += 1; // 左轉
if (turn == 2) U += 1; // 迴轉
if (turn == 3) R += 1; // 右轉（turn == 0 是直行，不計）
px = x;
py = y;
prevDir = dir;
}
cout << L << " " << R << " " << U << endl;
return 0;
}
測過再交：兩個範例裡一次「直行」都沒有
範例 2 蓋到了左轉、右轉、迴轉，但整條路徑每一步都在轉彎——「繼續直走」這個情況兩個範例都沒考。自己補測：
| 輸入 | 正確輸出 | 在測什麼 |
|---|---|---|
3 ／ 2 0、5 0、5 3 |
1 0 0 |
中途直行：第二段繼續向東，不能被數成任何一種轉彎 |
2 ／ 5 0、2 0 |
0 0 1 |
向西掉頭、但 \(x\) 還是正的：方向要跟上一個點比，不是跟原點比 |
4 ／ 3 0、3 4、3 1、6 1 |
2 0 1 |
左轉後迴轉再左轉：同一種轉彎出現兩次 |
三個都親眼看過正確，這題就穩了。
常犯錯誤
- 左轉右轉搞反：「面朝東時，北在左手邊」——想像自己站在路上，不要用看地圖的直覺。範例 1 當場現形（印
0 1 0，正確是1 0 0）。 - 忘了第一段就朝東：從第一個點才開始記方向，第一個點上的轉彎整個沒算到。範例 1 當場現形（印
0 0 0）。 - 直行也被數進去：編號差 \(0\) 什麼都不是，別把它跟迴轉混在一起。兩個範例都矇得過（範例裡沒有直行）——自測表第一列就是為它設計的。
- 負數取餘忘了先 \(+4\)：
(dir - prevDir) % 4算出 \(-1\)、\(-3\)，右轉和一半的迴轉都對不上號。範例 1 剛好只有左轉、照樣過；範例 2 會現形（印2 0 3，正確是2 1 5）。 - 方向跟原點比：第一個點剛好在 X 軸上，\(y\) 的比較兩種寫法一樣，範例 1 矇得過；「往西走但 \(x\) 還是正的」就會分不出迴轉和直行——自測表第二列就是為它設計的。