【題解】ZeroJudge e599: 10813 – Traditional BINGO

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=e599
【解題想法】模擬BINGO遊戲

  • mp[x] = {i, j}; 紀錄BINGO卡上,數字 x 出現的位置。
  • 每次主持人抽出來一個號碼,就用mp來判斷這個號碼是否存在BINGO卡上,如果有的話,把BINGO卡上對應位置的數字改成 0。
  • 檢查每個row/column/diagonal的數字總和,即可決定是否獲勝。
#include <iostream>
#include <vector>
#include <map>
using namespace std;
#define pii pair<int,int>
#define F first
#define S second
int a[5][5];

bool bingo(){
    int sum;
    //check rows
    for (int i = 0; i < 5; i++){
        sum = 0;
        for (int j = 0; j < 5; j++){
            sum += a[i][j];
        }
        if (sum == 0) return true;
    }
    //check columns
    for (int i = 0; i < 5; i++){
        sum = 0;
        for (int j = 0; j < 5; j++){
            sum += a[j][i];
        }
        if (sum == 0) return true;
    }
    //check diagonal-1
    sum = 0;
    for (int i = 0; i < 5; i++){
        sum += a[i][i];
    }
    if (sum == 0) return true;
    //check diagonal-2
    sum = 0;
    for (int i = 0; i < 5; i++){
        sum += a[i][4-i];
    }
    if (sum == 0) return true;
    return false;
}

int main() {
    int T;
    cin >> T;
    while (T--){
        map <int, pii> mp;
        for (int i = 0; i < 5; i++){
            for (int j = 0; j < 5; j++){
                if (i == 2 && j == 2){
                    a[2][2] = 0;
                    continue;
                }
                cin >> a[i][j];
                mp[a[i][j]] = {i, j};
            }
        }
        vector <int> v(75);
        for (int i = 0; i < 75; i++){
            cin >> v[i];
        }
        for (int i = 0; i < 75; i++){
            if (mp.count(v[i])) {
                auto now = mp[v[i]];
                a[now.F][now.S] = 0;
                if (bingo()) {
                    cout << "BINGO after " << i+1 << " numbers announced\n";
                    break;
                }
            }
        }
    }
}

Python code (credit: Amy Chou)

def check():
    for i in range(5):
        if len(set(M[i])) == 1:
            return True
    for j in range(5):
        col = [M[i][j] for i in range(5)]
        if len(set(col)) == 1:
            return True
    if len(set([M[i][i] for i in range(5)])) == 1:
        return True
    if len(set([M[i][4-i] for i in range(5)])) == 1:
        return True
    return False

T = int(input())
for Case in range(T):
    M = []
    for i in range(5):
        M.append(list(map(int, input().split())))

    M[2].insert(2, -1)
    dic = {}
    for i in range(5):
        for j in range(5):
            dic[M[i][j]] = (i, j)
            
    N = []
    while len(N) < 75:
        N.extend(list(map(int, input().split())))
    for i in range(75):
        if N[i] in dic:
            r, c = dic[N[i]]
            M[r][c] = -1
            if check():
                print(f"BINGO after {i+1} numbers announced")
                break
分享本文 Share with friends