#54667: C++ Easy AC


belubruh123 (belubruh123)


#include <bits/stdc++.h>
using namespace std;

// 檢查兩個相同數字是否可以消除
// loc: 單一數字的座標資訊 [狀態, r1, c1, r2, c2]
// map: 記錄所有數字狀態的 loc 陣列
// whole: 原始盤面 table
bool check(vector<int> &loc, vector<vector<int>>&map, vector<vector<int>>&whole) {
    // 水平檢查 (同一列)
    if (loc[1] == loc[3]) {
        if (loc[4] - loc[2] > 1) { // 如果兩個點不是緊緊相鄰
            // 掃描兩點之間的所有格子
            for (int i = loc[2] + 1; i < loc[2] + 1 + loc[4] - loc[2] - 1; i++) {
                // whole[loc[1]][i] 取得該格子的數字,再透過 map 去查該數字的狀態
                // 使用 +1 技巧:若狀態為 -1 (已消除),-1+1=0 (false) 通過;若為 1 (未消除),則阻擋
                if (map[whole[loc[1]][i]][0] + 1) {
                    return false;
                }
            }
        }
        return true;
    }
    // 垂直檢查 (同一行)
    if (loc[2] == loc[4]) {
        if (loc[3] - loc[1] > 1) {
            for (int i = loc[1] + 1; i < loc[1] + 1 + loc[3] - loc[1] - 1; i++) {
                if (map[whole[i][loc[2]]][0] + 1) {
                    return false;
                }
            }
        }
        return true;
    }
    return false;
}

int main() {
    // 關閉同步,加速 cin/cout 讀寫
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, m;
    int score = 0;
    bool valid = true;
    cin >> n >> m;
    
    // loc: 大小 1001 確保包含所有 0~1000 的數字,初始狀態設為 -1
    vector<vector<int>> loc(1001, vector<int>(1, -1));
    vector<vector<int>> table(n, vector<int>(m, 0));
    
    // 讀取盤面資料並記錄每個數字的位置
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int num;
            cin >> num;
            table[i][j] = num;
            loc[num].push_back(i); // 存入 Row
            loc[num].push_back(j); // 存入 Col
            loc[num][0] = 1;       // 更新狀態為 1 (存活)
        }
    }
    
    // 不斷掃描盤面,直到無法再消除任何數字為止
    while (valid) {
        valid = false;
        for (int i = 0; i < 1001; i++) {
            // 如果該數字存在且未被消除 (1 + 1 = 2 -> true)
            if (loc[i][0] + 1) {
                // 如果路徑暢通
                if (check(loc[i], loc, table)) {
                    valid = true;    // 觸發連鎖,設定下一輪繼續掃描
                    loc[i][0] = -1;  // 將數字標記為已消除
                    score += i;      // 加上對應分數
                }
            }
        }
    }
    cout << score;
    return 0;
}