f001 - Tic-Tac-Toe Solver
題目描述
題目要求找出所有符合井字遊戲規則的盤面。輸入一個包含 '-'、'X' 和 'O' 的字串，代表井字遊戲的盤面，其中 '-' 表示空格。程式需要找出所有可以填入 'X' 和 'O' 使得盤面符合井字遊戲規則的解，並輸出這些解的數量以及每個解的盤面。
解題思路
這題使用 backtracking 演算法來解決。dfs 函數遞迴地填入 'X' 或 'O' 到盤面的空格中。judge 函數檢查當前盤面是否符合井字遊戲的規則，包括 'X' 的數量必須是 4 個，'O' 的數量必須是 5 個，且沒有任何一行、一列或對角線上有三個相同的符號。如果盤面符合規則，則將其添加到答案字串 ans 中。
複雜度分析
- 時間複雜度: O(2^9) 因為每個空格都有兩種選擇 ('X' 或 'O')，總共有 9 個空格，所以時間複雜度是 O(2^9)。
- 空間複雜度: O(N) 其中 N 是所有有效盤面的數量。空間複雜度主要來自於儲存答案字串
ans。
程式碼
#include <iostream>
using namespace std;
string m,t,ans;
bool judge(){
int x=0,o=0;
for(int i=0;i<9;++i){
if(t[i]=='X')++x;
else if(t[i]=='O')++o;
else return 1;
}
if(x!=4||o!=5)return 1;
for(int i=0;i<9;i+=3){
if(t[i]==t[i+1]&&t[i+1]==t[i+2])return 1;
}
for(int i=0;i<3;++i){
if(t[i]==t[i+3]&&t[i]==t[i+6])return 1;
}
if(t[0]==t[4]&&t[4]==t[8])return 1;
if(t[2]==t[4]&&t[4]==t[6])return 1;;
return 0;
}
void dfs(int it){
if(it==9){
if(judge()==0)
ans+=t;
return;
}
if(m[it]=='-'){
t[it]='O';
dfs(it+1);
t[it]='X';
dfs(it+1);
}
else{
dfs(it+1);
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> m){
t=m;
ans="";
dfs(0);
int al=ans.length()/9;
cout << al << "\n" ;
for(int i=0;i<al;++i){
for(int j=0;j<9;++j){
cout << ans[i*9+j];
if(j%3==2)cout << "\n";
}
cout << "\n";
cout << "\n";
}
}
}