---
# System prepended metadata

title: APCS 202306 第一題 路徑偵測 (ZeroJudge k731)

---

# APCS 202306 第一題 路徑偵測 (ZeroJudge k731)
[ZJ題目連結](https://zerojudge.tw/ShowProblem?problemid=k731) (此題解先說明方法再揭示範例程式，包含python與C++)
## 方法說明
這題要計算在一個行進路線中的左轉/右轉/迴轉的次數，起點在座標$(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;
}

```