题意分析

问题要求判断给定的3×3井字棋棋盘状态是否可能出现在合法游戏过程中。核心是验证该状态是否符合游戏的基本规则和逻辑约束。

解题思路

1. 基本规则验证

   • 检查棋子数量关系（X比O多0或1个）
   • 确保不存在双方同时获胜的情况

2. 胜负状态验证

   • X获胜时必须满足X比O多1子
   • O获胜时必须满足X与O子数相同
   • 胜负后不能继续落子

3. 状态合法性验证

   • 不需要回溯模拟，通过规则约束即可判定
   • 重点检查棋子数量和胜负状态的匹配关系

实现步骤

1. 统计X和O的数量，验证数量关系
2. 分别检查X和O是否形成三连线
3. 验证胜负状态与棋子数量的匹配
4. 排除双方同时获胜的情况
5. 综合所有检查结果给出最终判断

代码实现

#include <iostream>
#include <vector>
#include <string>

using namespace std;

bool checkWin(const vector<string>& board, char player) {
    // Check rows
    for (int i = 0; i < 3; ++i) {
        if (board[i][0] == player && board[i][1] == player && board[i][2] == player) {
            return true;
        }
    }
    
    // Check columns
    for (int j = 0; j < 3; ++j) {
        if (board[0][j] == player && board[1][j] == player && board[2][j] == player) {
            return true;
        }
    }
    
    // Check diagonals
    if (board[0][0] == player && board[1][1] == player && board[2][2] == player) {
        return true;
    }
    if (board[0][2] == player && board[1][1] == player && board[2][0] == player) {
        return true;
    }
    
    return false;
}

bool isValidConfiguration(const vector<string>& board) {
    int xCount = 0, oCount = 0;
    
    // Count number of X's and O's
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (board[i][j] == 'X') {
                xCount++;
            } else if (board[i][j] == 'O') {
                oCount++;
            }
        }
    }
    
    // Check counts are valid
    if (oCount > xCount || xCount > oCount + 1) {
        return false;
    }
    
    bool xWins = checkWin(board, 'X');
    bool oWins = checkWin(board, 'O');
    
    // Both players can't win
    if (xWins && oWins) {
        return false;
    }
    
    // If X wins, must have one more X than O
    if (xWins && xCount != oCount + 1) {
        return false;
    }
    
    // If O wins, must have same count as X
    if (oWins && oCount != xCount) {
        return false;
    }
    
    return true;
}

int main() {
    int N;
    cin >> N;
    
    // Skip the first newline after N
    string line;
    getline(cin, line);
    
    for (int caseNum = 0; caseNum < N; ++caseNum) {
        vector<string> board;
        
        // Read 3 lines for the board
        for (int i = 0; i < 3; ++i) {
            getline(cin, line);
            board.push_back(line);
        }
        
        // Check if configuration is valid
        if (isValidConfiguration(board)) {
            cout << "yes" << endl;
        } else {
            cout << "no" << endl;
        }
        
        // Skip empty lines between cases (except after last case)
        if (caseNum != N - 1) {
            getline(cin, line); // read the empty line
        }
    }
    
    return 0;
}