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

gaoyangyang · 2025-07-14 21:10:28 · 题解

题目传送门

前往我的博客观看可能会更方便食用

拿到一道新题，我们还是需要秉持一个原则“先看懂题，再去做题”。

所以我们的第一步就是深度的了解题目，提取关键词，讲文字语言转化成编程语言。

理解题意

当我们再重读一遍题目后可以发现如下要点：

我们需要在 4 \times 4 的棋盘中找到一行（或一列，对角线）是同一种“棋子”（包括 'T'）。
输入中有且仅有 'X','O','T','.'四种。
最后输出有且仅有 X 胜利，O 胜利，平局和游戏尚未结束，从这里可以发现玩家 X 和玩家 O 其实是等价的，只需要判断好其中一个，复制即可。
题目中明确标注 “注意” 即使游戏结局已经可以明确预见，只要棋盘中存在空格且游戏尚未实际结束，都必须输出 "Game has not completed"（因为其重要性，所以这句话照抄）

到现在审题要点基本是看完了，因为如果你注意到你是因为审题问题而没有AC，现在不要往下翻，可以去修改代码了。

解题结构

细细的读完题目就需要开始解题了，解题我们应当由“宏观”到“微观”，即从代码框架入手，再补全细节。

经过审题，我们可以清晰的得到如下三步：

变量初始化，输入。
分析处理，判断结果属于哪种情况。
依照判断结果输出。

显然第二步是我们的重点，对于这类“全称量”条件（即比如一行全是同类字符）我给出如下建议(仅供参考)。

bool flag;//定义一个变量描述是否成立
flag=0;   //初始化，赋值为1也是可行的
for (int i;;)
{
    ......
}         //相关的判断以及处理，修改（或不修改）flag的值

//此时我们根据flag的值相应的输出（进行下一步操作）即可
if (flag)
{
    ......
{

我们可以想到分别判断行，列，对角线，用判断结果影响最终状态，以此得借，依照此思路，我们回归题目。

对于行的判断，只需要保证：存在一个 i 使得任意 j 的 (i,j) 均相等。

而对于列的判断，与行相似，只需要保证：存在一个 j 使得任意 i 的 (i,j) 均相等。

由于两者过于相似，所以可以一起判断（分开也不会错），参考代码如下。

for (int i=1;i<=4;i++)
{   
    lx=lo=hx=ho=1;//初始化行与列的状态变量
    for (int j=1;j<=4;j++)
    {
    if (_map[i][j]!='X' and _map[i][j]!='T')hx=0;
    if (_map[i][j]!='O' and _map[i][j]!='T')ho=0;
    if (_map[j][i]!='X' and _map[j][i]!='T')lx=0;
    if (_map[j][i]!='O' and _map[j][i]!='T')lo=0;   
    //相关处理

    if (hx==1 or lx==1)//更改关于X的最终状态
    {
        fx=1;break;
    }
    if (ho==1 or lo==1)//更改关于O的最终状态
    {
        fo=1;break;
    }
    }
}

对于由左上到右下对角线的情况，我们不难发现只需要判断是否所有的 (i,i) 均相等（通俗的讲）。

相似的，对于由右上到左下对角线的情况也就是判断是否所有的 (i,4-i+1) 均相等。

参考代码如下：

for (int i=1;i<=4;i++)
{
    if (_map[i][i]!='X' and _map[i][i]!='T' )zx=0;
    if (_map[i][i]!='O' and _map[i][i]!='T' )zo=0;
    if (_map[i][4-i+1]!='X' and _map[i][4-i+1]!='T' )yx=0;
    if (_map[i][4-i+1]!='O' and _map[i][4-i+1]!='T' )yo=0;      
}//此处初始化与对于最终状态的影响与前面行列过于相似，所以省略

最后如果判断下来 X 与 O 均没有赢，判断棋盘中是否还有空位，相应的进行输出即可。

参考代码展示：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n;
bool fx,fo,d;
bool hx,ho,zx,zo,yx,yo,lx,lo;
char _map[5][5];
int main()
{
    cin>>n;
    for (int T=1;T<=n;T++)
    {
        fx=fo=d=0;
        hx=ho=zx=zo=yx=yo=lx=lo=1;
        for (int i=1;i<=4;i++)
        {
            for (int j=1;j<=4;j++)
            {
                cin>>_map[i][j];
                if (_map[i][j]=='.')d=1;//判断是否有空位 
            }
        }
        for (int i=1;i<=4;i++)//对角线 
        {
            if (_map[i][i]!='X' and _map[i][i]!='T' )zx=0;
            if (_map[i][i]!='O' and _map[i][i]!='T' )zo=0;
            if (_map[i][4-i+1]!='X' and _map[i][4-i+1]!='T' )yx=0;
            if (_map[i][4-i+1]!='O' and _map[i][4-i+1]!='T' )yo=0;      
        }       
        for (int i=1;i<=4;i++)//行与列 
        {   
            lx=lo=hx=ho=1;
            for (int j=1;j<=4;j++)
            {
                if (_map[i][j]!='X' and _map[i][j]!='T')hx=0;
                if (_map[i][j]!='O' and _map[i][j]!='T')ho=0;
                if (_map[j][i]!='X' and _map[j][i]!='T')lx=0;
                if (_map[j][i]!='O' and _map[j][i]!='T')lo=0;   
            }
            if (hx==1 or lx==1)
            {
                fx=1;break;
            }
            if (ho==1 or lo==1)
            {
                fo=1;break;
            }
        }

        if (hx==1 or lx==1 or zx==1 or yx==1)//最后的判断 
            fx=1;
        if (ho==1 or lo==1 or zo==1 or yo==1)
            fo=1;

        if (fx==1)//输出 
            printf("Case #%d: X won\n",T);
        else if (fo==1)
            printf("Case #%d: O won\n",T);
        else if (fx==0 and fo==0 and d==0)
            printf("Case #%d: Draw\n",T);
        else
            printf("Case #%d: Game has not completed\n",T);
    }
    return 0;
}

谢谢观看，如果有帮助到你，请留下一个赞吧~