d431 - 第三題: 賓果遊戲 (bingo)
題目描述
題目要求模擬賓果遊戲，讀取兩個 5x5 的賓果卡 (A 和 B) 以及 25 個叫號數字的順序。在每次叫號後，檢查 A 和 B 是否達到賓果 (一行、一列或對角線全為 0)。輸出最先達到賓果的一方 (A 或 B 或 AB 平手) 以及達成賓果的最後一個叫號數字。
解題思路
程式使用兩個 5x5 的陣列 a 和 b 分別儲存賓果卡 A 和 B。程式讀取 25 個叫號數字，每次叫號後，在 a 和 b 中將對應的數字設為 0。然後，程式檢查 a 和 b 是否達到賓果。檢查賓果的條件包括：
- 檢查主對角線和副對角線是否全為 0。
- 檢查每一行是否全為 0。
- 檢查每一列是否全為 0。 如果 A 先達到賓果，則輸出 "A" 和最後一個叫號數字。如果 B 先達到賓果，則輸出 "B" 和最後一個叫號數字。如果 A 和 B 同時達到賓果，則輸出 "AB" 和最後一個叫號數字。
複雜度分析
- 時間複雜度: O(n^3)，其中 n 是賓果卡的大小 (本題為 5)。因為有 25 次叫號，每次叫號需要遍歷 5x5 的陣列來尋找數字並設為 0，然後需要遍歷陣列來檢查賓果。
- 空間複雜度: O(n^2)，因為需要儲存兩個 5x5 的賓果卡。
程式碼
#include <iostream>
using namespace std;
int a[5][5],b[5][5],t,ba,bb,sum3,sum4;
int main(){
for(int i=0;i<5;++i)
for(int j=0;j<5;++j)
cin >> a[i][j];
for(int i=0;i<5;++i)
for(int j=0;j<5;++j)
cin >> b[i][j];
for(int i=0;i<25;++i){
cin >> t;
for(int i=0;i<5;++i)
for(int j=0;j<5;++j)
if(t==a[i][j]){
a[i][j]=0;
i=5;j=5;
}
for(int i=0;i<5;++i)
for(int j=0;j<5;++j)
if(t==b[i][j]){
b[i][j]=0;
i=5;j=5;
}
sum3=0;sum4=0;
for(int j=0;j<5;++j){
sum3+=a[j][j];
sum4+=a[j][4-j];
}
if(sum3==0)++ba;
if(sum4==0)++ba;
for(int i=0;i<5;++i){
int sum=0,sum2=0;
for(int j=0;j<5;++j){
sum+=a[i][j];
sum2+=a[j][i];
}
if(sum==0)++ba;
if(sum2==0)++ba;
}
sum3=0;sum4=0;
for(int j=0;j<5;++j){
sum3+=b[j][j];
sum4+=b[j][4-j];
}
if(sum3==0)++bb;
if(sum4==0)++bb;
for(int i=0;i<5;++i){
int sum=0,sum2=0;
for(int j=0;j<5;++j){
sum+=b[i][j];
sum2+=b[j][i];
}
if(sum==0)++bb;
if(sum2==0)++bb;
}
if(ba>=5&&bb>=5){
cout << "AB " << t ;
break;
}
else if(ba>=5){
cout << "A " << t;
break;
}
else if(bb>=5){
cout << "B " << t;
break;
}
ba=0;bb=0;
}
}