b005 - 布林矩陣的等價短陣
題目描述
題目要求判斷一個布林矩陣是否為等價短陣，即每一行和每一列的和是否都為偶數。如果不是，則判斷是否只改變一個位元就能使其成為等價短陣。如果無法通過改變一個位元使其成為等價短陣，則輸出 "Corrupt"。
解題思路
程式首先讀取矩陣的大小 n，然後讀取矩陣的元素。接著，程式遍歷每一行，計算每一行的和。如果某一行和為奇數，則記錄該行的索引。同樣地，程式遍歷每一列，計算每一列的和。如果某列和為奇數，則記錄該列的索引。
如果沒有找到奇數行和或奇數列和，則矩陣已經是等價的，輸出 "OK"。如果找到一個奇數行和和一個奇數列和，則改變該行該列的位元，使其成為等價短陣，輸出 "Change bit (行索引, 列索引)"。如果找到多個奇數行和或奇數列和，則表示無法通過改變一個位元使其成為等價短陣，輸出 "Corrupt"。
複雜度分析
- 時間複雜度: O(n^2)，因為需要遍歷整個矩陣來計算行和和列和。
- 空間複雜度: O(n^2)，因為需要儲存整個矩陣。
程式碼
#include <iostream>
using namespace std;
int main(){
int a;
while(cin >> a){
bool b[a][a],ans=0;
for(int i=0;i<a;i++)
for(int j=0;j<a;j++)
cin >> b[i][j];
int x=0,y=0,xb=-1,yb=-1;
for(int i=0;i<a;i++){
for(int j=0;j<a;j++)
x+=b[i][j];
if(x%2){
if(xb!=-1)
ans=1;
xb=i;
x=0;
}
}
for(int j=0;j<a;j++){
for(int i=0;i<a;i++)
y+=b[i][j];
if(y%2){
if(yb!=-1)
ans=1;
yb=j;
y=0;
}
}
if(ans==1)
cout << "Corrupt\n" ;
else if(xb==-1&&yb==-1)
cout << "OK\n";
else
cout << "Change bit (" << xb+1 << "," << yb+1 << ")\n";
}
}