開啟章節選單

卡牌遊戲

https://zerojudge.tw/ShowProblem?problemid=m371

題意

在一個 $n \times m$ 大小的表格上每格裡都有一張牌
你可以水平或垂直消除數值為 $x$ 的兩張牌並獲得 $x$ 分，但中間不能有其他牌
求最多能獲得多少分

想法

枚舉每張牌，嘗試上或左匹配是否存在相同的牌即可
使用 $-1$ 紀錄已經匹配掉的牌

至於為什麼只要匹配左上不用考慮右下
是因為左跟右、還有上跟下是相對關係

考點

主要考點
- 二維陣列
先備知識

程式碼

#include <bits/stdc++.h>

using namespace std;

int tb[50][50]; // 表格

signed main() {
    int n, m;
    cin >> n >> m;
    // 輸入資料
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> tb[i][j];
        }
    }
    int ans = 0;
    // 重複執行匹配動作至少 n*m 次以配對所有卡牌
    for (int _ = 0; _ < 1000; _++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (tb[i][j] == -1) continue;
                // 嘗試往上配對
                if (i > 0) {
                    int k = i-1;
                    while (k > 0 && tb[k][j] == -1) k--;
                    if (tb[i][j] == tb[k][j]) {
                        // 配對成功
                        ans += tb[i][j]; // 增加分數
                        tb[i][j] = tb[k][j] = -1; // 將兩張牌紀錄乘已匹配
                        continue; // 匹配成功後即可忽略這張牌
                    }
                }
                // 嘗試往左配對
                if (j > 0) {
                    int k = j-1;
                    while (k >= 0 && tb[i][k] == -1) k--;
                    if (tb[i][j] == tb[i][k]) {
                        // 配對成功
                        ans += tb[i][j]; // 增加分數
                        tb[i][k] = tb[i][j] = -1; // 將兩張牌紀錄乘已匹配
                        continue; // 匹配成功後即可忽略這張牌
                    }
                }
            }
        }
    }
    cout << ans << endl;
}