# APCS實作題2023年6月第1題：路徑偵測 > 日期：2023年9月26日 > 作者：王一哲 > 題目來源：112年6月實作題第1題 > [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=k731) <br /> ## 題目 ### 問題描述 給一個二維平面，座標如同數學的二維座標(Ｙ正為北，Ｘ正為東)。起始位置在 (0, 0)，接下來會有 $n$ 個座標，你需要按照這些座標點的順序移動，保證僅會垂直或水平方向上移動，不會斜向移動，且第一個點保證一定是Ｘ軸正的位置（初始方向向右）。 請輸出這條路徑中，左轉、右轉、迴轉的個數分別為多少。 配分 - 60%：$n = 2$ - 40%：$n \leq 100$ <br /> ### 輸入說明 第一行輸入一個正整數 $n$，接下來有 $n$ 行，每一行都有兩個正整數 $x, y$。保證的是相鄰兩個點的座標差值不超過 100。 <br /> ### 輸出說明 輸出三個正整數，分別代表左轉、右轉、迴轉的次數。 <br /> ### 範例一：輸入 ``` 2 2 0 2 1 ``` ### 範例一：正確輸出 ``` 1 0 0 ``` <br /> ### 範例二：輸入 ``` 9 4 0 4 9 4 8 4 10 4 2 4 3 6 3 6 10 6 9 ``` ### 範例二：正確輸出 ``` 2 1 5 ``` <br /> ## Python 程式碼 於 ZeroJudge 測試結果，最長運算時間約為 23 ms，使用記憶體最多約為 3.4 MB，通過測試。 ```python= def findDir(xc, yc, xp, yp): # 回傳前進方向 if xc > xp and yc == yp: return 1 # 向右 elif xc == xp and yc > yp: return 2 # 向上 elif xc < xp and yc == yp: return 3 # 向左 elif xc == xp and yc < yp: return 4 # 向下 else: return 0 def turn(dc, dp): # 回傳轉彎種類 if (dp == 1 and dc == 2) or (dp == 2 and dc == 3) or (dp == 3 and dc == 4) or (dp == 4 and dc == 1): return 1 # 左轉 elif (dp == 1 and dc == 4) or (dp == 4 and dc == 3) or (dp == 3 and dc == 2) or (dp == 2 and dc == 1): return 2 # 右轉 elif (dp == 1 and dc == 3) or (dp == 3 and dc == 1) or (dp == 2 and dc == 4) or (dp == 4 and dc == 2): return 3 # 迴轉 else: return 0 n = int(input()) # 讀取資料行數 xp, yp = 0, 0 # 前一次的位置 L, R, U = 0, 0, 0 # 分別為左轉、右轉、迴轉次數 xc, yc = map(int, input().split()) # 目前的位置 dp = findDir(xc, yc, xp, yp) # 前一次的前進方向 xp, yp = xc, yc # 更新 xp, yp for _ in range(1, n): # 依序讀取第 2 ~ n 筆資料 xc, yc = map(int, input().split()) # 目前的位置 dc = findDir(xc, yc, xp, yp) # 找出目前的前進方向 T = turn(dc, dp) # 由前進方向找出轉彎種類 if T == 1: L += 1 # 右轉 elif T == 2: R += 1 # 左轉 elif T == 3: U += 1 # 迴轉 xp, yp, dp = xc, yc, dc # 更新 xp, yp, yp print("{:d} {:d} {:d}".format(L, R, U)) # 印出答案 ``` <br /><br /> ## C++ 程式碼 於 ZeroJudge 測試結果，最長運算時間約為 3 ms，使用記憶體最多約為 332 kB，通過測試。 ```cpp= #include <iostream> using namespace std; int findDir(int xc, int yc, int xp, int yp) { // 回傳前進方向 if (xc > xp && yc == yp) return 1; // 向右 else if (xc == xp && yc > yp) return 2; // 向上 else if (xc < xp && yc == yp) return 3; // 向左 else if (xc == xp && yc < yp) return 4; // 向下 else return 0; } int turn(int dc, int dp) { // 回傳轉彎種類 if ((dp == 1 && dc == 2) || (dp == 2 && dc == 3) || (dp == 3 && dc == 4) || (dp == 4 && dc == 1)) return 1; // 左轉 else if ((dp == 1 && dc == 4) || (dp == 4 && dc == 3) || (dp == 3 && dc == 2) || (dp == 2 && dc == 1)) return 2; // 右轉 else if ((dp == 1 && dc == 3) || (dp == 3 && dc == 1) || (dp == 2 && dc == 4) || (dp == 4 && dc == 2)) return 3; // 迴轉 else return 0; } int main() { int n; cin >> n; // 讀取資料行數 int xp = 0, yp = 0; // 前一次的位置 int L = 0, R = 0, U = 0; // 分別為左轉、右轉、迴轉次數 int xc, yc; cin >> xc >> yc; // 目前的位置 int dp, dc, T; // 分別為前一次的前進方向、目前的前進方向、轉彎種類 dp = findDir(xc, yc, xp, yp); // 前一次的前進方向 xp = xc; yp = yc; // 更新 xp, yp for(int i=1; i<n; i++) { // 依序讀取第 2 ~ n 筆資料 cin >> xc >> yc; // 目前的位置 dc = findDir(xc, yc, xp, yp); // 找出目前的前進方向 T = turn(dc, dp); // 由前進方向找出轉彎種類 if (T == 1) L++; // 右轉 else if (T == 2) R++; // 左轉 else if (T == 3) U++; // 迴轉 xp = xc; yp = yc; dp = dc; // 更新 xp, yp, yp } cout << L << " " << R << " " << U << endl; // 印出答案 return 0; } ``` <br /><br /> --- ###### tags:`APCS`、`Python`、`C++`