题解：P13281 [GCJ 2013 Qualification] Tic-Tac-Toe-Tomek

这是一道模拟题，对于模拟题要分析题意，简单概括就是以下三点：

在4×4棋盘上判断胜负，我们需要对所有行、列和两条对角线进行检查；
胜利条件：当某行/列/对角线包含4个相同符号，或3个相同符号加1个T时，判定是哪一方胜利；
存在空格且无胜负时则返回未结束状态。

对于棋盘存储，在 [CSP-J 2024] 地图探险的宝贵经验告诉我们，用二维数组存储棋盘状态。

对于两方胜负判定，我们分主体来判定。对于每一方，我们分别检测以下四种题目中提及的情况：

横向四连
纵向四连
主对角线四连
副对角线四连

同时按照题意，将‘T’做为通配符，检测一方胜利时就当做那一方的棋子进行判定。

跟据判定胜负的情况来决定输出什么（详情见代码）。

代码如下：

CPP

#include <iostream>
using namespace std;
bool check_win(char board[4][4], char player) {  //player代表检测哪一方
    //检查行与列
    for (int i = 0; i < 4; ++i) {
        bool row_win = true, col_win = true;
        for (int j = 0; j < 4; ++j) {
            if (board[i][j] != player && board[i][j] != 'T') 
                row_win = false;
            if (board[j][i] != player && board[j][i] != 'T')
                col_win = false;
        }
        if (row_win || col_win) return true;
    }
    //检查对角线
    bool diag1 = true, diag2 = true;
    for (int i = 0; i < 4; ++i) {
        if (board[i][i] != player && board[i][i] != 'T')
            diag1 = false;
        if (board[i][3-i] != player && board[i][3-i] != 'T')
            diag2 = false;
    }
    return diag1 || diag2;
}
int main() {
    int T;
    cin >> T;
    for (int t = 1; t <= T; ++t) {
        char board[4][4];
        for (int i = 0; i < 4; ++i)
            for (int j = 0; j < 4; ++j)
                cin >> board[i][j];
        bool x_won = check_win(board, 'X');//第一方的胜负情况
        bool o_won = check_win(board, 'O');//第二方的胜负情况
        bool has_empty = false;
        for (int i = 0; i < 4; ++i)
            for (int j = 0; j < 4; ++j)
                if (board[i][j] == '.') has_empty = true;
        cout << "Case #" << t << ": ";
        //根据双方胜负情况来判定
        if (x_won) cout << "X won";
        else if (o_won) cout << "O won";
        else if (has_empty) cout << "Game has not completed";
        else cout << "Draw";
        cout << endl;
    }
    return 0;
}

时间复杂度

O(T)

，可以通过此题。

题解：P13281 [GCJ 2013 Qualification] Tic-Tac-Toe-Tomek

文章操作

相关推荐

评论

题解：P13281 [GCJ 2013 Qualification] Tic-Tac-Toe-Tomek