# APCS實作題2023年10月第2題：卡牌遊戲

> 日期：2024年1月30日
> 作者：王一哲
> 題目來源：2023年10月實作題第2題
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=m371)

## 題目

### 問題描述

你有一個 $n \times m$ 大小的表格，你可以從中消除具有相同數值且之間沒有障礙物的兩個元素，並獲得分數。請問你可以獲得的最大得分。

每一種數字在表格中出現恰好兩次。消除兩個相同的數字 $x$ 時，可以獲得 $x$ 分。

消除規則：你可以垂直或水平地將兩個相同數值的元素消除，但消除的兩個元素之間不能有其他尚未消除的元素。
<br />

### 輸入說明

第一行包含兩個整數：$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$ 。
<br />

### 輸出說明

請輸出一個整數，代表你可以獲得的最大得分。
<br />

### 範例輸入1

1 8
0 2 3 3 0 2 5 5

### 範例輸出1

8

<br />

### 範例輸入2

3 6
0 2 3 8 0 2
1 1 4 4 5 7
5 6 3 8 6 7

### 範例輸出2

29

<br />

## Python 程式碼

費時最久約為 55 ms，使用記憶體最多約為 3.4 MB，通過測試。

n, m = map(int, input().split())  # 讀取卡牌列數n、欄數m
cards = [list(map(int, input().split())) for _ in range(n)]  # 讀取卡牌數字
pos = [(r, c) for r in range(n) for c in range(m)]  # 産生所有的位置並存成串列
score = 0  # 總分
flag = True  # 是否繼續執行，如果有找到配對成功的兩張牌即為 True
while flag:  # 當 flag 為 True 時繼續執行
    flag = False  # 先重設為 False
    for r, c in pos:  # 依序讀取位置 (r, c)
        if cards[r][c] == -1: continue  # 如果這個位置的牌已取走已被設定為 -1，執行下一次 for 迴圈
        nr, nc = r+1, c+1  # 下一列 nr，下一欄 nc
        """ 向下找相同的牌 """
        while nr < n-1 and cards[nr][c] == -1: nr += 1  # 如果 nr 還可以加 1 而且這個位置的牌已取走，將 nr 加 1
        if nr <= n-1 and cards[nr][c] == cards[r][c]:  # 如果 nr 沒有出界，而且 {nr, c}、{r, c} 兩張牌相同
            score += cards[r][c]  # score 加上牌面數字
            cards[r][c] = -1  # 將這兩個位置的牌設為 -1
            cards[nr][c] = -1
            flag = True  # flag 設定為 True，繼續找下一輪
        """ 向右找相同的牌 """
        while nc < m-1 and cards[r][nc] == -1: nc += 1  # 如果 nc 還可以加 1 而且這個位置的牌已取走，將 nc 加 1
        if nc <= m-1 and cards[r][nc] == cards[r][c]:  # 如果 nc 沒有出界，而且 {n, nc}、{r, c} 兩張牌相同
            score += cards[r][c]  # score 加上牌面數字
            cards[r][c] = -1  # 將這兩個位置的牌設為 -1
            cards[r][nc] = -1
            flag = True  # flag 設定為 True，繼續找下一輪
# 結束 while 迴圈
print(score)  # 印出答案

<br /><br />

## C++ 程式碼

費時最久約為 6 ms，使用記憶體最多約為 328 kB，通過測試。

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

int main() {
    int n, m; cin >> n >> m;  // 讀取卡牌列數n、欄數m
    vector<vector<int>> cards (n, vector<int> (m, 0));  // 卡牌數字
    vector<pair<int, int>> pos (n*m, make_pair(0, 0));  // 所有的位置
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            int card; cin >> card;
            cards[i][j] = card;
            pos[i*m+j] = {i, j};
        }
    }
    int score = 0;  // 總分
    bool flag = true;  // 是否繼續執行，如果有找到配對成功的兩張牌即為 True
    while(flag) {  // 當 flag 為 True 時繼續執行
        flag = false;  // 先重設為 False
        for(auto p : pos) {  // 依序讀取位置 (r, c)
            int r = p.first, c = p.second;
            if (cards[r][c] == -1) continue;  // 如果這個位置的牌已取走已被設定為 -1，執行下一次 for 迴圈
            int nr = r+1, nc = c+1;  // 下一列 nr，下一欄 nc
            /* 向下找相同的牌 */
            while(nr < n-1 && cards[nr][c] == -1) nr++;  // 如果 nr 還可以加 1 而且這個位置的牌已取走，將 nr 加 1
            if (nr <= n-1 && cards[nr][c] == cards[r][c]) {  // 如果 nr 沒有出界，而且 {nr, c}、{r, c} 兩張牌相同
                score += cards[r][c];  // score 加上牌面數字
                cards[r][c] = -1;  // 將這兩個位置的牌設為 -1
                cards[nr][c] = -1;
                flag = true;  // flag 設定為 True，繼續找下一輪
            }
            /* 向右找相同的牌 */
            while(nc < m-1 && cards[r][nc] == -1) nc++;  // 如果 nc 還可以加 1 而且這個位置的牌已取走，將 nc 加 1
            if (nc <= m-1 && cards[r][nc] == cards[r][c]) {  // 如果 nc 沒有出界，而且 {n, nc}、{r, c} 兩張牌相同
                score += cards[r][c];  // score 加上牌面數字
                cards[r][c] = -1;  // 將這兩個位置的牌設為 -1
                cards[r][nc] = -1;
                flag = true;  // flag 設定為 True，繼續找下一輪
            }
        }
    }
    cout << score << "\n";  // 印出答案
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`Python`、`C++`