【APCS】2023年6月實作題 C++ 解題筆記（前兩題）

此筆記僅供個人學習用途，內容僅供參考。

---

1. https://zerojudge.tw/ShowProblem?problemid=k731

題目說明：

給定一個如數學座標一樣的二維平面（y 正為北, x 正為東），起始位置於 $(0, 0)$ 。輸入給 $n$ 個座標，必須按照這些點的順序移動，題目保證只會垂直或水平方向移動，不會斜向移動。且第一個點保證一定是 x 軸正的位置(初始方向向右)。

請輸出這條路徑中，左轉、右轉、迴轉的個數分別為多少。

解題思路：

1. 定義方向：
   • 0：東。
   • 1：北。
   • 2：西。
   • 3：南。
2. 計算方向：
   • 根據相鄰兩點的座標變化，去判斷移動方向。如：若 x 不變，y 增加，則方向為北（1）；若 x 增加，y 不變，則方向為東（0）。
3. 判斷轉向：
   • 每點 $p_i$ （ $i$ 從 $1$ 到 $n-1$ ），分別計算兩個方向：
     • 進入方向 d1：從 $P_{i-1}$ 到 $P_i$ 。
     • 離開方向 d2：從 $Pi$ 到 $P_{i+1}$ 。
   • 判斷 d1, d2 變化量 dir：
     • dir = (d2 - d1 + 4) % 4
     • dir == 1：左轉
     • dir == 3：右轉
     • dir == 2：迴轉
     • dir == 0：無轉向

#include <bits/stdc++.h>

using namespace std;

int get_direction(pair<int, int> p1, pair<int, int> p2){
    if (p1.first == p2.first){ // x 座標相同
        if (p2.second > p1.second) return 1; // p2 y 座標 > p1 y 座標，表示向北
        else return 3; // p2 y 座標 < p1 y 座標，表示向南
    }
    else{ // y 座標相同
        if (p2.first > p1.first) return 0; // p2 x 座標 > p1 x 座標，表示向東
        else return 2; // p2 x 座標 < p1 x 座標，表示向西
    }
    return -1;
}

int main(){
    int n;
    cin >> n;
    
    vector <pair<int, int>> p;
    
    p.push_back({0, 0});
    
    for (int i = 0; i < n; i++){
        int x, y;
        cin >> x >> y;
        p.push_back({x, y});
    }
    
    int left = 0, right = 0, u_turn = 0;
    
    for (int i = 1; i < n; i++){
        int d1 = get_direction(p[i-1], p[i]); // 進入方向
        int d2 = get_direction(p[i], p[i+1]); // 離開方向
        int dir = (d2 - d1 + 4) % 4; // 判斷轉向
        if (dir == 1) left++;
        else if (dir == 3) right++;
        else if (dir == 2) u_turn++; // 這邊不要寫成 else 了，因為還有 dir == 0 的情形
    }
    
    cout << left << " " << right << " " << u_turn;
    
    return 0;
}

int dir = (d2 - d1 + 4) % 4; 這條後面的 + 4 是避免方向差 d2 - d1 出現負數的情況，另外用 % 4 取模運算確保落在範圍 $[0, 3]$ 。

至於為何要 d2 - d1 呢？

• 左轉：+ 90 度。
• 右轉：- 90 度。
• 迴轉：+ 180 度或 - 180 度都算迴轉。

因為左轉、右轉等等這些都是需要搭配兩點去判斷的，如果我們知道兩點的角度差，就可以去判斷是左轉還右轉，那這個角度差其實可以用方向來表示（題目保證只有水平跟垂直，所以不管怎樣走都是 90 度），例如 d1 向西（2）、d2 向北（1），還是 d1 向北（1）、d2 向西（2），他們之間的差值都是 1，只是會有正負問題，那這樣我們就可以定義 1 為左轉，剩下的依此類推。

---

1. https://zerojudge.tw/ShowProblem?problemid=k732

題目說明：

給定一個 $n \times m$ 二維矩陣 $a$ ，每個元素 $a[i][j]$ 的值為 $x (0 \leq x \leq 9)$ 。對於位置 $(i, j)$ ，若以 $(i, j)$ 為中心，曼哈頓距離 $\leq x$ 的所有點的數值總和對 $10$ 取模等於 $x$ ，則稱 $(i, j)$ 為特殊位置。

曼哈頓距離定義：設兩點 $(a, b), (c, d)$ ，則其曼哈頓距離為 $|a - c| + |b - d|$ 。

解題思路：

這題可用 BFS 優化，但老話一句，這是 APCS 第二題，所以你懂的，可以用暴力解 :)。

1. 判斷特殊位置：
   • 獲取該位置的值 $x = a[i][j]$ 。
   • 計算所有曼哈頓距離 $\leq x$ 的點（含 $(i, j)$ ）的數值總和。
   • 檢查總和對 $10$ 取模是否 $= x$ 。
   • 若滿足上述條件，紀錄該特殊位置（記得建一個 vector 來記錄，然後用 pair 容器）。
2. 計算曼哈頓距離：
   • 設兩點 $(p, q)$ ，用來找所有曼哈頓距離 $\leq x$ 的點，並累計 $a[p][q]$ 的數值總和。
   • 曼哈頓距離： $|i - p| + |j - q| \leq x$
   • 找 p 點範圍：
     • p 要讓 $|i - p| \leq x$ 。
     • 拆開絕對值後： $i - x \leq p \leq i + x$ 。
     • 要注意 p 他是索引值，所以範圍要再改一下： $0 \leq p \leq n - 1$ 。
     • 最後才會變成以下程式碼：
     • for (int p = max(0, i - x); p <= min(n - 1, i + x); p++)
   • 找 q 點範圍：
     • 把 p 點固定，令 $|i - p| = dp$ ，則 $|j - q| \leq x - dp = d$ 。
     • 所以 q 滿足 $j - d \leq q \leq j + d$ 。
     • q 也是索引值，所以：
     • for (int q = max(0, j - dp); q <= min(m - 1, j + dp); q++)
     • 另外 int dp = x - abs(i - p); 。

註：這個 dp 不是那個 dynamic programming，是代表 i 跟 p 之間的距離。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

int main(){
    
    int n, m;
    cin >> n >> m;
    vector <vector<int>> a(n, vector<int>(m));
    
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> a[i][j];
            
    vector <pair<int, int>> special; // 用 pair 容器表示點座標
    
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            
            int x = a[i][j];
            int sum = 0;
            
            // 枚舉曼哈頓距離小於等於 x 的點
            // 用 max 跟 min 是防止超過邊界
            // max(0, i - x) 代表最小不能小於第 0 列
            // min(n - 1, i + x) 代表最大不能超過第 n-1 列
            for (int p = max(0, i - x); p <= min(n - 1, i + x); p++){
                int dp = x - abs(i - p);
                
                for (int q = max(0, j - dp); q <= min(m - 1, j + dp); q++){
                    sum += a[p][q];
                }
            }
            
            if (sum % 10 == x){
                special.emplace_back(i, j);
            }
        }
    }
    
    cout << special.size() << '\n';
    
    for (auto [i, j] : special){
        cout << i << " " << j << '\n';
    }
    
    return 0;
}

這題比較麻煩的是要推導曼哈頓距離的不等式，之後再透過寫程式的方式枚舉所有可能點。