---
tags: 解題報告,zj
---

# k731. 1. 路徑偵測
題目連結: [Zerojudge](https://zerojudge.tw/ShowProblem?problemid=k731)

## 題目說明
計算給定座標所形成的路徑有幾個左轉、右轉及迴轉
## 想法
一種轉向由兩個移動方向所組成
要決定 左轉/右轉/迴轉 必須知道**上一個移動的方向**及**下一個移動的方向**
而決定移動的方向則是跟座標變化有關
若將 左轉/右轉/迴轉 的所有情況枚舉出來可得以下這張圖
每種轉向都有四種形式

圖中的箭頭方向分別代表 $x$ 軸與 $y$ 軸的增減
若將這四種箭頭編號並帶入圖中可得

結論:
只要判斷兩個箭頭的狀態即可得知其轉向

## 參考答案
:::spoiler CPP

struct Move{
    int from_x, from_y, to_x, to_y;
    int d;// {1: x+, 2: x-, 3: y+, 4:y-}
   Move(){}
   Move(int from_x, int from_y, int to_x, int to_y){
    if (from_x != to_x){
        if (from_x < to_x) d = 1;
        else d = 2;
    }
    else{
        if (from_y < to_y) d = 3;
        else d = 4;
    }
   }
};

int x=0, y=0;
int n, tx, ty;
int tl=0, tr=0, tb=0; // turn left/right/back

void solve(){
    cin>>n;
    cin>>x>>y;
    Move m1(0, 0, x, y);
    n--;
    while (n--){
        cin>>tx>>ty;
        Move m2(x, y, tx, ty);
        if (
            (m1.d == 1 and m2.d == 3) or
            (m1.d == 2 and m2.d == 4) or
            (m1.d == 3 and m2.d == 2) or
            (m1.d == 4 and m2.d == 1))
            tl++;
        else if (
            (m1.d == 1 and m2.d == 4) or
            (m1.d == 2 and m2.d == 3) or
            (m1.d == 3 and m2.d == 1) or
            (m1.d == 4 and m2.d == 2))
            tr++;
        else if (
            (m1.d == 3 and m2.d == 4) or
            (m1.d == 4 and m2.d == 3) or
            (m1.d == 1 and m2.d == 2) or
            (m1.d == 2 and m2.d == 1))
            tb++;
        m1 = m2;
        x = tx;
        y = ty;
    }
    cout<<tl<<" "<<tr<<" "<<tb<<"\n";
}

[Github](https://github.com/henryleecode23/solve_record/blob/main/zerojudge/k731/k731.cpp)
:::

## 補充
為了更明確表示移動
使用了`struct`建立`Move`
並在建構函式中完成狀態的判斷

---
{%hackmd @hlc23/dark-theme %}
{%hackmd @hlc23/dark-theme-license %}