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

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

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

題目說明：

該水杯可以被視為上下兩段直立長方體所組成：

下半段：底面積 $w1 \times w1$ ，高 $h1$ 。
上半段：底面積 $w2 \times w2$ ，高 $h2$ 。

倒水時：

水先填滿下半段，接著填上半段。

每次倒入的體積 $v$ ，轉換為水位高度上升量（根據在哪一段來決定用哪段的底面積去除體積，得到水位高度）。

解題思路：

1. 先計算兩段的容量（下、上）。
2. 記錄目前水位高度。
3. 模擬每一次倒入：
- 判斷水還在下半段還是已經進入上半段。
- 根據當前段的底面積換算水位上升高度。
- 水滿之後不再上升。
4. 記錄每次倒水所產生的「水位上升高度」，並取最大值輸出。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n; // 倒水次數

    int w1, w2, h1, h2;
    cin >> w1 >> w2 >> h1 >> h2; // 下半段及上半段的寬高

    vector<int> pours(n);
    for (int i = 0; i < n; ++i) {
        cin >> pours[i]; // 每次倒入的體積
    }

    // 計算下半段與上半段的總容量
    int volume1 = w1 * w1 * h1; // 下半段
    int volume2 = w2 * w2 * h2; // 上半段
    int totalVolume = volume1 + volume2; // 總容量

    int currentVolume = 0; // 目前杯子已裝入水的總體積
    int maxRise = 0; // 水位上升最高一次的高度變化量

    for (int i = 0; i < n; ++i) {
        int v = pours[i]; // 本次所倒入的體積
        int oldVolume = currentVolume; // 紀錄倒水前體積
        currentVolume += v; // 更新倒水後的體積
        
        // 判斷水是否倒滿
        if (currentVolume > totalVolume) {
            currentVolume = totalVolume;
        }

        int rise = 0; // 該次水位上升的高度

        // 判斷水在哪段（下段/上段）上升，並計算對應的高度變化
        if (oldVolume < volume1 && currentVolume <= volume1) {
            // 落於下半段
            rise = (currentVolume - oldVolume) / (w1 * w1);
        } else if (oldVolume < volume1 && currentVolume > volume1) {
            // 下半段滿了, 但有部分到達上半段
            // part1 計算下半段的水位
            int part1 = (volume1 - oldVolume) / (w1 * w1);
            // part2 計算上半段的水位
            int part2 = (currentVolume - volume1) / (w2 * w2);
            rise = part1 + part2;
        } else {
            // 上半段全滿
            rise = (currentVolume - oldVolume) / (w2 * w2);
        }

        // 更新最大水位變化
        if (rise > maxRise) {
            maxRise = rise;
        }
    }

    cout << maxRise;
    return 0;
}

2. https://zerojudge.tw/ShowProblem?problemid=o712

題目說明：

你有一張 $M \times N$ 的地圖，每一格有一些寶石（或牆壁）。
有一個機器人從某個位置出發，一開始朝**右邊**，按照這些規則移動：

1. 如果格子是 $0$ 顆寶石，機器人會停下來。
2. 如果有寶石，加到分數並撿走一顆（格子上的數量 $-1$ ）。
3. 如果現在的分數是 $k$ 的倍數，機器人就會 右轉 $90$ 度。
4. 如果他正前方是 牆壁或邊界外，就繼續右轉，直到找到能走的格子，然後繼續。

最後輸出總共撿了幾顆寶石。

另外：

1. 轉彎的時機是撿完寶石且加分數後。
2. 要確保走的格子 不是牆壁 (-1) 且 不出界。

解題思路：

1. 設二維 vector 變數 grid 存地圖。
2. 用一個向量陣列來記錄方向 dx, dy，代表四個方向（右、下、左、上）。
3. 機器人邏輯設計：
- 如果當前位置寶石數是 0，停止。
- 否則將寶石數加到 score，並將該格寶石數量減 1。
- 如果 score % k == 0，右轉（方向 +1）。
- 往該方向走，如果遇到牆壁或出界，就持續右轉直到可以走為止。

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int M, N, k, r, c;
    cin >> M >> N >> k >> r >> c;
    
    vector<vector<int>> grid(M, vector<int>(N));
    for (int i = 0; i < M; ++i)
        for (int j = 0; j < N; ++j)
            cin >> grid[i][j];
    
    //           右 下 左 上
    int dx[4] = {0, 1, 0, -1}; // 0 : 不動, 1: 動一格, -1: 退一格
    int dy[4] = {1, 0, -1, 0};
    
    // dx 為行與行(row) 之間的移動, 會跳到下一個 vector
    // dy 為列與列(column) 之間的移動, 會在同一個 vector 中不同元素跳動
    
    int dir = 0; // 紀錄目前方向, 預設朝右
    int score = 0, gems = 0;

    while (true) {
        // 如果當前格子寶石為 0, 跳出迴圈
        if (grid[r][c] == 0)
            break;
        
        // 加分與撿寶石
        score += grid[r][c];
        grid[r][c]--;
        gems++;
        
        // 是否右轉
        if (score % k == 0)
            dir = (dir + 1) % 4;
        
        // 找下一個可以走的方向
        for (int i = 0; i < 4; ++i) {
            // 嘗試從目前方向 dir 移動，計算新位置 (nr, nc)
            int nr = r + dx[dir];
            int nc = c + dy[dir];
            
            // 邊界檢查 + 檢查是否遇到牆 (grid[nr][nc] != -1)
            if (nr >= 0 && nr < M && nc >= 0 && nc < N && grid[nr][nc] != -1) {
                r = nr;
                c = nc;
                break;
            }
            dir = (dir + 1) % 4; // 右轉
        }
    }
    
    cout << gems;
    return 0;
}