神题，我是以前花了一周时间才写出minmax，有经验所以补上alpha-beta就会容易一些。（虽然alpha-beta剪枝也很难）
所以题解就不写了，想学minmax的话网上有很多现成的。
1 #include<iostream> 2 using namespace std; 3 4 int row,col,chess; 5 char board[5][5]; 6 7 int minSearch(int i,int j,int alpha); 8 int maxSearch(int i,int j,int beta); 9 10 11 bool check(int r,int c){ 12 if( board[r][0]==board[r][1] && board[r][1]==board[r][2] && board[r][2]==board[r][3] && board[r][3]!='.' ) return true; 13 if( board[0][c]==board[1][c] && board[1][c]==board[2][c] && board[2][c]==board[3][c] && board[3][c]!='.' ) return true; 14 15 if( board[0][3]==board[1][2] && board[1][2]==board[2][1] && board[2][1]==board[3][0] && board[0][3]==board[r][c] ) return true; 16 if( board[0][0]==board[1][1] && board[1][1]==board[2][2] && board[2][2]==board[3][3] && board[0][0]==board[r][c] ) return true; 17 return false; 18 } 19 20 int minSearch(int i,int j,int alpha){ //minsearch返回所有子结点中的【最小值】 alpha代表它父亲兄弟结点的最大值 21 //上一步走在了(i,j)，要判断【这个棋子】能不能让棋局结束 22 if( check(i,j) ) return 1;//x下完就结束了，x胜 23 if( chess==16 ) return 0; 24 25 26 27 28 int beta = 1;//这个里面放所以子结点的最小值 == 因为是min结点 == 一开始得很大 29 for(int i=0;i<4;i++) 30 for(int j=0;j<4;j++) 31 if( board[i][j]=='.' ){ 32 board[i][j] = 'o'; chess++; 33 34 beta = min(beta, maxSearch(i,j,beta) );//第三个参数是 == 目前min结点兄弟结点中的最小值 35 36 board[i][j] = '.'; chess--; 37 if( alpha>= beta ) return beta; 38 } 39 return beta; 40 } 41 42 int maxSearch(int i,int j,int beta){//beta是上一层兄弟结点中的最小值 43 if( check(i,j) ) return -1; 44 if( chess==16 ) return 0; 45 46 int alpha = -1;//记录所有子结点中的最大值 47 for(int i=0;i<4;i++) 48 for(int j=0;j<4;j++) 49 if( board[i][j]=='.' ){ 50 board[i][j] = 'x'; chess++; 51 52 alpha = max( alpha,minSearch(i,j,alpha) );//alpha是我兄弟结点的最大值 53 54 board[i][j] = '.'; chess--; 55 if( alpha>=beta ) return alpha; 56 } 57 return alpha; 58 } 59 60 61 62 bool solve(){ 63 64 int alpha=-1;//一开始最大值很小 == 根结点 == 根结点的子结点都剪不了 65 for(int i=0;i<4;i++) 66 for(int j=0;j<4;j++) 67 if( board[i][j]=='.' ){ 68 board[i][j] = 'x'; chess++; 69 70 int tmp = minSearch(i,j,alpha);//第三个是alpha代表它兄弟结点的最大值 ， 但root没有兄弟节点 71 72 board[i][j] = '.'; chess--; 73 // cout<<i<<" "<<j<<" "<<tmp<<endl; 74 //cout<<i<<" "<<j<<endl; 75 if(tmp==1) { row=i; col=j; return true; } 76 } 77 78 return false; 79 } 80 81 82 int main(){ 83 84 85 while(1){ 86 chess=0; 87 char op; cin>>op; 88 if(op=='$') break; 89 for(int i=0;i<4;i++) 90 for(int j=0;j<4;j++) { 91 cin>>board[i][j]; 92 if(board[i][j]!='.') chess++; 93 } 94 95 if( solve() ) cout<<"("<<row<<","<<col<<")"<<endl; 96 else cout<<"#####"<<endl; 97 } 98 99 100 }