d576 - 辭典遊戲
題目描述
題目描述了一個兩人輪流從一個 N x N 的棋盤上取數字的遊戲。玩家 A 總是先從第一列開始，玩家 B 則從玩家 A 取走數字的那一列開始。遊戲持續進行，直到其中一方無法再取數字為止。最終，總和較高的玩家獲勝。題目要求計算所有可能的遊戲進行方式中，A 獲勝、B 獲勝和平手的次數。
解題思路
這道題可以使用深度優先搜尋 (DFS) 來模擬所有可能的遊戲過程。dfs 函數模擬了遊戲的進行，參數 x 和 y 代表當前棋盤上的位置，as 和 bs 分別代表 A 和 B 取得的總和，round 記錄了當前是第幾回合（奇數回合 A 走，偶數回合 B 走）。
在 dfs 函數中，首先標記當前位置為已訪問，然後根據回合數更新 A 或 B 的總和。接著，遞迴地探索所有可能的下一個位置。如果沒有可行的下一個位置，則判斷 A 和 B 的總和，並更新對應的獲勝次數。最後，將當前位置標記為未訪問，以便回溯到上一層。
主函數中，讀取棋盤的數字，初始化獲勝次數，然後從第一列的每個位置開始進行 DFS 搜尋。最後，輸出 A 獲勝、B 獲勝和平手的次數。
複雜度分析
- 時間複雜度: O(N! * N!)。在最壞的情況下，需要探索所有可能的遊戲過程，這涉及到 N! 種可能的 A 的走法，以及在每種 A 的走法下，B 的 N! 種走法。
- 空間複雜度: O(N * N)。主要用於儲存棋盤狀態
p和np，以及 DFS 的遞迴堆疊。
程式碼
#include <iostream>
using namespace std;
int p[5][5],n,awin,bwin,tie,np[5][5];
inline void dfs(int x,int y,int as,int bs,int round){
int stp=0;
np[x][y]=1;
if(round&1){
as+=p[x][y];
for(int i=0;i<n;++i)
if(!np[i][y]){
dfs(i,y,as,bs,round+1);
stp=1;
}
}
else{
bs+=p[x][y];
for(int i=0;i<n;++i)
if(!np[x][i]){
dfs(x,i,as,bs,round+1);
stp=1;
}
}
if(stp==0){
if(as>bs)
++awin;
else if(bs>as)
++bwin;
else
++tie;
}
np[x][y]=0;
return;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> n){
for(int i=0;i<5;++i)
for(int j=0;j<5;++j)
np[i][j]=p[i][j]=0;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
cin >> p[i][j];
awin=bwin=tie=0;
for(int i=0;i<n;++i)
dfs(0,i,0,0,1);
cout << awin << " " << bwin << " " << tie << "\n";
}
}