# APCS 202306 第一題 路徑偵測 (ZeroJudge k731)
[ZJ題目連結](https://zerojudge.tw/ShowProblem?problemid=k731) (此題解先說明方法再揭示範例程式，包含python與C++)
###### tags: `apcs`
## 方法說明
這題要計算在一個行進路線中的左轉/右轉/迴轉的次數，起點在座標$(0,0)$然後輸入一連串$n$個點座標。根據題意，連續兩點之間車輛只會往上下左右的某一個方向移動(而且一定會移動)，這些限制使得題目較為簡單。
要決定一個轉彎，我們需要連續的兩個方向，例如，東轉南是右轉、東轉北是左轉、東轉西是迴轉，而如果方向沒有改變則沒有任何轉彎。因此，要找出轉彎，我們必須先計算出方向。
要找出兩點之間的行進方向，我們需要兩點的座標。若前一點的座標為$(px,py)$，目前座標為$(x,y)$，那麼
1. $x>px$: 往東
2. $x<px$: 往西
3. $y>py$: 往北
4. $y<py$: 往南
對於第一子題，點數$n=2$且保證遞一個方向是向東，因此我們可以用4個if來計算出第二個方向，就可以決定是左轉、右轉、迴轉或是沒有轉彎。
對於第二子題來說，因為有多個不確定個數的點，我們需要使用一個迴圈來處理，迴圈每一次處理一個方向計算一個轉彎，在迴圈的尾端，我們需要為下一次做準備，需要把**目前的方向**改成**前一個方向**，把**目前的點座標**改成**前一個點座標**。主要流程如下：
```
輸入n與px,py
prev_dir = 東
repeat n-1 times:
input x,y
根據px,py,x,y計算dir
根據prev_dir,dir計算轉彎並記錄
px = x, py = y, prev_dir = dir
end of loop
輸出答案
```
**小技巧：** 在根據prev_dir,dir計算轉彎時，一共有16種狀況要判斷(4種方向 * 4種方向)，這裡我們可以將方向順時針或逆時針訂為0,1,2,3，這樣利用兩個方向的差就可以決定轉彎。例如，我們方向東南西北訂為0123，那麼$dir - prev\_dir = 1$就是右轉，為了解決相減為負(0-3是北轉東為右轉)，我們可以用$(dir - prev\_dir+4)\%4$ 來決定轉彎。
## 第一子題
為了初學者我們先單獨說明第一子題的範例程式。因為第一子題只有兩點而且第一個方向必定向東，因此只需要決定第二個方向就可以算出轉彎的種類。以下是Python與C++的範例程式。
### Python code
```python=
n = int(input())
x1,y1 = map(int,input().split()) #first point
x2,y2 = map(int,input().split()) #second point
# first direction must be East
# we need to know the second direction
if x2>x1: # East -> East; no turn
print(0,0,0)
elif y2>y1: # East -> North; turn left
print(1,0,0)
elif y2<y1: # East -> South; turn right
print(0,1,0)
else: # East -> West; turn around; backward
print(0,0,1)
```
留意在一行讀入兩個整數的方法。
### C++ code
```cpp=
// s1, n==2
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, x,y,px,py;
cin >> n;
cin >>px>>py; // px>0 and py=0, east
cin >>x>>y;
if (x > px) cout << "0 0 0\n"; //east -> east; no turn
else if (x < px) cout << "0 0 1\n"; // east -> west; turn around
else if (y > py) cout << "1 0 0\n"; // east -> north; turn left
else cout << "0 1 0\n"; // east -> south; turn right
return 0;
}
```
## 完全解
### Python code
```python=
'''
we need previous point (px,py) and current point (x,y)
previous direction prev_d and current direction d
# direction: 0,1,2,3 = east, south, west, north
'''
n = int(input())
px,py = map(int,input().split()) #first point
prev_d = 0 #first dir=East
left,right,back = 0,0,0 # count the turns
for i in range(n-1):
x,y = map(int,input().split()) #current point
#determine current dir
if x > px: d = 0
elif y < py: d = 1
elif x < px: d = 2
else: d = 3
# determine turn
turn = (d-prev_d)%4
if turn==3: left += 1
elif turn==1: right += 1
elif turn==2: back += 1
# current point become previous point of the next
px,py = x,y
prev_d = d
#end for
print(left,right,back)
```
左右與迴轉需要各用一個變數記錄他的次數，Python的負數對正數取餘數會回到正值，所以第18行寫turn = (d-prev_d)%4就可以，當然寫turn = (d-prev_d+4)%4也沒問題。
### C++ code
```cpp=
/* we need previous point (px,py) and current point (x,y)
previous direction prev_d and current direction d
direction: 0,1,2,3 = east, south, west, north
*/
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, x,y,px,py,dir,prev_dir=0; // first dir = east
int left=0,right=0,rev=0;
cin >> n >>px >>py;
for (int i=1;i<n;i++) {
cin >> x>> y;
if (x > px) dir = 0; // East
else if (y < py) dir = 1; //South
else if (x < px) dir = 2; //West
else dir = 3; //North y>py
// using dir and prev_dir to determine turn
if (dir == (prev_dir+1)%4) right++;
else if (dir==(prev_dir+2)%4) rev++;
else if (dir==(prev_dir+3)%4) left++;
// else no direction changed
// current -> previous for next point
prev_dir = dir;
px = x, py =y;
}
cout << left<<' '<<right<<' '<<rev<<'\n';
return 0;
}
```
Sign in with Wallet
Connect another wallet