541 Error Correction

題目連結

題目敘述

當一個布林矩陣的每一列與每一欄的總和皆為偶數（即包含偶數個為 1 的位元）時
我們稱此矩陣通過奇偶校驗（parity property）
以下是一個通過奇偶校驗的 4×4 矩陣：

1 0 1 0
0 0 0 0
1 1 1 1
0 1 0 1

每列的總和為 2、0、4 和 2，每欄的總和為 2、2、2 和 2

你的工作是撰寫一個程式，讀入一個矩陣並檢查其是否通過奇偶校驗
如果沒有，程式應檢查是否可以僅透過改變一個位元來通過校驗
如果這也不可能，則該矩陣應被歸類為損毀（corrupt）

輸入說明

輸入檔將包含一個或多個測資
每組測資的第一行包含一個整數 n（n < 100），代表矩陣的大小
接下來的 n 行中，每行會有 n 個整數
矩陣中只會出現 ‘0’ 和 ‘1’。當 n 為 0 時，表示輸入結束

輸出說明

對於輸入中的每個矩陣，輸出一行。若矩陣已具奇偶特性，輸出 ‘OK’
若僅需更改一個位元即可達成奇偶特性，輸出 ‘Change bit (i,j)’，其中 i 為列號，j 為欄號（1-based）
否則輸出 ‘Corrupt’。

解題思路

計算每直行、橫列的總和為奇數的次數，記為 r, c
接下來判斷以下三種情況：

1. 若 r 與 c 皆為 0，代表陣列已經符合
2. 若 r 與 c 剛好為 1，代表只需要將那陣列，即可通過校驗
3. 以上兩種情況皆不符合，則代表此矩陣被歸類為損毀（corrupt）

針對以上不同的情況輸出相應結果即可

程式碼

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

int main() {
    int n;
    while (scanf("%d", &n), n) {
        vector<vector<int>> v(n, vector<int>(n));
        for (auto &i : v) for (auto &j : i) scanf("%d", &j);
        int x, y, r, c; r = c = 0;
        // x, y 用來記錄總和為奇數是第幾橫列、第幾直行
        // r, c 用來記錄橫列、直行總和為奇數的次數
        for (int i = 0; i < n; i++) { // 檢查橫列
            int cnt = 0;
            for (int j = 0; j < n; j++) cnt += v[i][j]; // 計算總和
            if (cnt&1) r++, x = i+1; // 若總和為奇數就紀錄
        }
        for (int i = 0; i < n; i++) { // 檢查直行
            int cnt = 0;
            for (int j = 0; j < n; j++) cnt += v[j][i]; // 計算總和
            if (cnt&1) c++, y = i+1; // 若總和為奇數就紀錄
        }
        if (r == 1 && c == 1) printf("Change bit (%d,%d)\n", x, y);
        else if (!r && !c) printf("OK\n");
        else printf("Corrupt\n");
    }
}