https://zerojudge.tw/ShowProblem?problemid=m371
題意#
在一個 \(n \times m\) 大小的表格上每格裡都有一張牌
你可以水平或垂直消除數值為 \(x\) 的兩張牌並獲得 \(x\) 分，但中間不能有其他牌
求最多能獲得多少分
想法#
枚舉每張牌，嘗試上或左匹配是否存在相同的牌即可
使用 \(-1\) 紀錄已經匹配掉的牌
至於為什麼只要匹配左上不用考慮右下
是因為左跟右、還有上跟下是相對關係
考點#
- 主要考點
- 二維陣列
- 先備知識
- C++ 的程式結構
- 變數的使用方式
- 條件判斷
- 基本運算
- 基本輸入
- 基本輸出
- 數學函式
- For 迴圈
- 迴圈控制
程式碼#
#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;
}
