专栏文章

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

ggaoyangyang
P13281题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miow51ap
此快照首次捕获于
2025/12/03 02:07
3 个月前
此快照最后确认于
2025/12/03 02:07
3 个月前
查看原文
题目传送门
前往我的博客观看可能会更方便食用
拿到一道新题，我们还是需要秉持一个原则“先看懂题，再去做题”。
所以我们的第一步就是深度的了解题目，提取关键词，讲文字语言转化成编程语言。

理解题意

当我们再重读一遍题目后可以发现如下要点：
  • 我们需要在 4×44 \times 4 的棋盘中找到一行（或一列，对角线）是同一种“棋子”（包括 'T'）。
  • 输入中有且仅有 'X','O','T','.'四种。
  • 最后输出有且仅有 X 胜利，O 胜利，平局和游戏尚未结束，从这里可以发现玩家 X 和玩家 O 其实是等价的，只需要判断好其中一个，复制即可。
  • 题目中明确标注 “注意” 即使游戏结局已经可以明确预见，只要棋盘中存在空格且游戏尚未实际结束，都必须输出 "Game has not completed"（因为其重要性，所以这句话照抄）
到现在审题要点基本是看完了，因为如果你注意到你是因为审题问题而没有AC，现在不要往下翻，可以去修改代码了。

解题结构

细细的读完题目就需要开始解题了，解题我们应当由“宏观”到“微观”，即从代码框架入手，再补全细节。
经过审题，我们可以清晰的得到如下三步：
  1. 变量初始化，输入。
  2. 分析处理，判断结果属于哪种情况。
  3. 依照判断结果输出。
显然第二步是我们的重点，对于这类“全称量”条件（即比如一行 全 是同类字符）我给出如下 建议(仅供参考)。
CPP
bool flag;//定义一个变量描述是否成立
flag=0;   //初始化，赋值为1也是可行的
for (int i;;)
{
    ......
}         //相关的判断以及处理，修改（或不修改）flag的值

//此时我们根据flag的值相应的输出（进行下一步操作）即可
if (flag)
{
    ......
{
我们可以想到分别判断行，列，对角线，用判断结果影响最终状态，以此得借，依照此思路，我们回归题目。
对于行的判断，只需要保证：存在一个 ii 使得任意 jj 的 (i,j)(i,j) 均相等。
而对于列的判断，与行相似，只需要保证：存在一个 jj 使得任意 ii 的 (i,j)(i,j) 均相等。
由于两者过于相似，所以可以一起判断（分开也不会错），参考代码如下。
CPP
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,i) 均相等（通俗的讲）。
相似的，对于由右上到左下对角线的情况也就是判断是否所有的 (i,4−i+1)(i,4-i+1) 均相等。
参考代码如下：
CPP
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;		
}//此处初始化与对于最终状态的影响与前面行列过于相似，所以省略
最后如果判断下来 XX 与 OO 均没有赢，判断棋盘中是否还有空位，相应的进行输出即可。
参考代码展示：
CPP
#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;
}
谢谢观看，如果有帮助到你，请留下一个赞吧~

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...