# 2023/10 APCS 實作題

# 第一題 - 機械鼠
:::info
https://zerojudge.tw/ShowProblem?problemid=m370
:::

## 題目
有 $n$ 個位置上有食物，另外有一隻老鼠一開始位於位置 $x$。
老鼠在開始覓食前要選擇今天要往左邊或 往右移動去尋找食物，經過食物時可以停 下來吃食物，吃完後可以選擇繼續往相同 方向移動，或者是結束今天的覓食。
請問老鼠最多能吃到多少個食物，以及最 後停下來吃食物的位置。

## 輸入說明:
第一行包含兩個整數：$x$ 和 $n$，以空 格分隔。$x$ 代表老鼠的初始位置，$n$ 代表食物的數量。
第二行包含 $n$ 個整數，以空格分隔，表示每個食物的位置，且不會與老鼠位置重 疊。
所有測試資料皆保證 $3 \leq n \leq 20$ 且 $n$ 是奇數，老鼠與食物位置範圍均 為 $-100$ 到 $100$。
子題分數：
60%：滿足 $n = 3$。
40%：一般情況。

## 輸出說明:
請輸出兩個整數，分別代表最多能吃到的 食物數目和最後一個吃的食物停下的位置 。
## 解題絲路
排序後去比較:
1. 0~x比較多還是
2. x~n比較多

#include <bits/stdc++.h>
#define io ios::sync_with_stdio(0);cin.tie(0);
using namespace std;

int main(){io;
    int x,n;
    cin >> x >> n;
    vector<int> li(n+1);
    for (int i=0;i<n;++i)cin >> li[i];
    li[n] = x;
    sort(li.begin(),li.end());

    auto it = find(li.begin(), li.end(), x);
    int idx = distance(li.begin(),it);
    int mx = max((n-idx),(idx));

    cout << mx << " ";

    if (mx == idx)cout << li[0];
    else cout << li[li.size()-1];
}

# 第二題 - 卡牌遊戲
:::info
https://zerojudge.tw/ShowProblem?problemid=m371
:::

## 題目
你有一個 $n \times m$ 大小的表格，你 可以從中消除具有相同數值且之間沒有障 礙物的兩個元素，並獲得分數。請問你可 以獲得的最大得分。
每一種數字在表格中出現恰好兩次。消除 兩個相同的數字 $x$ 時，可以獲得 $x$ 分。
消除規則：你可以垂直或水平地將兩個相 同數值的元素消除，但消除的兩個元素之 間不能有其他尚未消除的元素。

## 輸入說明:
第一行包含兩個整數：$n$ 和 $m$，以空 格分隔。它們分別代表表格的行數和列數 。
接下來有 $n$ 行，每行包含 $m$ 個整數 ，以空格分隔，表示表格中的元素。每個 元素的數值範圍介於 $[0, 1000]$ 之內，且每種數字在表格中出現恰好兩次。
輸入保證表格上的每種數字恰好出現兩次 ，且表格的格數為偶數。
子題分數：
60%：滿足 $n = 1, 1 \leq m \leq 40$。
40%：滿足 $1 \leq n \leq 20, 1 \leq m \leq 40$。

## 輸出說明:
請輸出一個整數，代表你可以獲得的最大 得分。
## 解題絲路
用迴圈去遍歷每個元素，走到該元素時判斷兩件事:
1. 右邊元素是否相同
2. 下面元素是否相同

如果相同，就加上分數後，將兩個元素都改成1001
**之後遇到1001就穿越他**

迴圈停止條件為:
**直到找不到相鄰的兩元素** => 適合用while迴圈。
設一布林值，如果該布林值在此次迴圈未被修改，表示已經沒有可以消去的相鄰元素了。

#include <bits/stdc++.h>
#define io ios::sync_with_stdio(0);cin.tie(0);
using namespace std;

int graph[25][45] = {};

int main() {
    io
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> graph[i][j];
        }
    }

    int cnt = 0;
    bool changed = true;
    
    while (changed) {
        changed = false;

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (graph[i][j] == 1001) continue;
                int tmpi = i + 1, tmpj = j + 1;

                while (tmpi < n && graph[tmpi][j] == 1001) tmpi++;
                if (tmpi < n && graph[i][j] == graph[tmpi][j]) {
                    cnt += graph[i][j];
                    graph[i][j] = graph[tmpi][j] = 1001;
                    changed = true;
                }

                while (tmpj < m && graph[i][tmpj] == 1001) tmpj++;
                if (tmpj < m && graph[i][j] == graph[i][tmpj]) {
                    cnt += graph[i][j];
                    graph[i][j] = graph[i][tmpj] = 1001;
                    changed = true;
                }
            }
        }
        if (!changed) break;
    }

    cout << cnt;
}

:::info
這種解法稱為: 模擬
就是一步步去拓展並求解。
:::
---

:::info
趁機宣傳一下我自己的個人網站跟Youtube頻道 !!
**[個人網站](https://hyc.eshachem.com/) | [Youtube頻道](https://www.youtube.com/@Hy.C)**
:::
@2025 Hy.C 陳毓
> Copyright ©Hy.C 陳毓 CC BY-NC-SA 4.0 | 禁止商業用途 | 轉載標記出處 | 改 編作品必須在相同條款下分享。