b548 - 4.賓果遊戲
題目描述
題目描述了一個賓果遊戲的場景，要求模擬遊戲過程，並根據給定的策略輸出下一個應該選擇的號碼。策略是選擇一個未標記的號碼，使得標記該號碼後盤面的分數最高。如果有多個號碼可以達到最高分數，則選擇數值最小的那個。
解題思路
程式首先讀取賓果盤面的初始狀態，然後讀取玩家已經叫過的號碼。對於每個未標記的號碼，程式會模擬標記該號碼後的盤面，並計算盤面的分數（即有多少行、列或對角線被完全標記）。程式會記錄每個號碼標記後的分數，並選擇分數最高的號碼。如果有多個號碼具有最高分數，則選擇數值最小的號碼。
複雜度分析
- 時間複雜度: O(N * 25 * 5) ，其中 N 是叫過的號碼數量。最壞情況下，需要遍歷所有未標記的號碼，並對每個號碼模擬標記後的盤面，計算分數。
- 空間複雜度: O(1) ，程式使用的額外空間是固定的，不隨輸入大小變化。主要空間用於儲存盤面和一些臨時變數。
程式碼
#include <stdio.h>
int main(){
int a[5][5],n,s[26],max=0;
for(int i=0;i<26;i++)
s[i]=0;
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
scanf("%d",&a[i][j]);
while(1){
scanf("%d",&n);
if(n==-1)break;
for(int i=0;i<5&&n>0;i++){
for(int j=0;j<5&&n>0;j++){
if(a[i][j]==n){
n=0;
a[i][j]=n;
}
}
}
}
for(int i=0;i<5;i++){
for(int j=0;j<5;j++){
if(a[i][j]!=0){
int k=a[i][j],x=0,y=0,xx=0,yy=0;
a[i][j]=0;
for(int z=0;z<5;z++){
x+=a[z][j];
y+=a[i][z];
xx+=a[z][z];
yy+=a[4-z][z];
}
if(x==0)
s[k]++;
if(y==0)
s[k]++;
if(i==j&&xx==0)
s[k]++;
if(i+j==4&&yy==0)
s[k]++;
if(s[k]>max)
max=s[k];
a[i][j]=k;
}
}
}
for(int i=0;i<26;i++){
if(s[i]==max){
printf("%d",i);
break;
}
}
}