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

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

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

題目說明：

有 $n$ 個角色，分別都有攻擊力（ $a_i$ ）跟防禦力（ $d_i$ ）。

能力值 = $a{i}^{2} + d{i}^{2}$ 。

輸出第二大的能力值的角色的攻擊力跟防禦力。

解題思路：

1. 建立三個 vector：a, d, state，分別存每個角色的攻擊力、防禦力、能力值。
2. 由於要求第二大，再加上預設排序函式都是升序，要降序就用反向迭代器 rbegin() 跟 rend()。
3. 因為測資沒很大，直接遍歷找 (a[i]*a[i] + d[i]*d[i]) == state[1]。
4. cout 並 break，後面再找就沒意思。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    
    int n;
    cin >> n;
    
    vector <int> a(n);
    vector <int> d(n);
    vector <int> state(n);
    
    for (int i = 0; i < n; i++){
        cin >> a[i] >> d[i];
        state[i] = a[i]*a[i] + d[i]*d[i];
    }
    
    sort(state.rbegin(), state.rend());
    
    for (int i = 0; i < n; i++){
        
        if ((a[i]*a[i] + d[i]*d[i]) == state[1]){
            cout << a[i] << " " << d[i];
            break;
        }
        
    }
    return 0;
}

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

題目說明：

經過英文字母的路徑要全部輸出，第二行要輸出不重複字母的數字。

有個 $m \times n$ 的蜂巢，每個蜂巢的格子都有大寫或小寫的英文字母。

起始點在左下角，行走方向定義如圖：

1. 不用刻意做一個 $m \times n$ 的地圖，只要用內建的 string 型態跑一次迴圈就好。
2. 存放路徑用 string path，紀錄不重複字母使用 set 資料結構，會自動篩掉重複的元素。
3. 設兩種變數，一種是舊的 x, y（row, column），一種是新（目前在走的）的 x, y。
   • 注意 x = m - 1, y = 0，起始點在左下角。
4. 看範例圖去做移動的部分，像 A 往 T 就是往方向 0 移動一格，所以僅 x-- 就好。
5. 每次移動完，x = new_x, y = new_y;，更新舊 x y。

#include <bits/stdc++.h>

using namespace std;

int main(){
    int m, n, k;
    cin >> m >> n >> k;
    
    vector <string> hive(m);
    
    for (int i = 0; i < m; i++){ // 這邊特別注意, 只要一層迴圈即可
        cin >> hive[i];
    }
    
    string path;
    set <char> ans;
    
    int x = m - 1, y = 0; // 起始值在左下角
    
    int new_x = x, new_y = y;
    
    for (int i = 0; i < k; i++){
        
        int dir;
        cin >> dir;
        
        if (dir == 0){
            new_x--;
        }
        else if (dir == 1){
            new_y++;
        }
        else if (dir == 2){
            new_x++;
            new_y++;
        }
        else if (dir == 3){
            new_x++;
        }
        else if (dir == 4){
            new_y--;
        }
        else{
            new_x--;
            new_y--;
        }
        
        // new_x > (m - 1) || new_y > (n - 1) 需特別注意
        // 不小心就會寫成 new_x > m || new_y > n
        if (new_x < 0 || new_y < 0 || new_x > (m - 1) || new_y > (n - 1)){
            path += hive[x][y];
            ans.insert(hive[x][y]);
            new_x = x;
            new_y = y;
        }
        else{
            path += hive[new_x][new_y];
            ans.insert(hive[new_x][new_y]);
        }
        
        x = new_x;
        y = new_y;
        
    }
    
    cout << path << '\n';
    cout << ans.size();
    
    return 0;
}