正经题解｜井字棋

题目大意

本题为多组样例测试

给出一个$3 \times 3$的矩阵，矩阵仅有三个字符.,X,O所组成，代表两个人在$3 \times 3$的矩阵上下棋的棋局，X为先手,O为后手,.为未下棋地块。以任意方向放满三个棋子为结束的标志。

请你判断给出的$3 \times 3$的矩阵是否可能会在两者对局当中出现，每组样例给出YES与NO的回答。

题意分析

根据给出的棋盘进行判断是否为合法的棋盘即可。

解题思路

矩阵最大为$3 \times 3$，我们可以通过枚举所有的情况来判断棋盘是否为合法的。

首先我们需要理清楚，怎样的棋盘为合法的，怎样的棋盘为非合法的。

• X为先手，O为后手，那么在整个合法棋盘当中X的数量必然大于等于O，并且X下过之后O必然会添上一个，那么在整盘的棋局当中，X的数量只会比O多一个或者相等。
• 任意方向三个格子相同字符为结束，那么在一个合法棋盘当中，不可能出现两个人都获胜的情况。

我们还可以根据第二个条件继续衍生出两种不合法情况。

• 假若X获得胜利，那么此时X的数量必然不与O相等。
• 假若O获得胜利，那么此时O的数量必然不可能比X小1个。

整理出以上条件之后，我们只需要判断X与O之间的数量关系，再根据两者的获胜状态判断数量关系即可得出答案。

时间复杂度解析

本题使用循环对矩阵进行枚举，时间复杂度为$O(n^2)$

代码演示

#include<bits/stdc++.h>
using namespace std;

char mp[5][5];
int col[5][3];
int row[5][3];

void solve()
{
		memset(col,0,sizeof col);
		memset(row,0,sizeof row);
		int cnt1,cnt2;
		cnt1 = cnt2 = 0 ;
		for(int i = 0 ; i < 3 ; i ++)
		{
			for(int j = 0 ; j < 3 ; j ++ )
			{
				cin >> mp[i][j] ;
				if(mp[i][j] == 'X'){
					cnt1 ++ ;
					row[i][0]++;
					col[j][0]++;
				}
				else if(mp[i][j] == 'O'){
					cnt2 ++ ;
					row[i][1]++;
					col[j][1]++;
				}
			}
		}
		if(cnt1 - cnt2 > 1 || cnt1 < cnt2)
		{
			cout << "No" << endl;
			return;
		}
		bool f1,f2;
		f1=f2=false;
		for(int i = 0 ; i < 3 ; i ++ )
		{
			if(row[i][0] >= 3)f1=true;
			if(col[i][0] >= 3)f1=true;
			if(row[i][1] >= 3)f2=true;
			if(col[i][1] >= 3)f2=true;
		}
		if(mp[1][1] == mp[2][2] && mp[1][1] == mp[0][0]){
			if(mp[1][1] == 'X')f1=true;
			else if(mp[1][1] == 'O')f2 = true;
		}
		if(mp[0][2] == mp[1][1] && mp[1][1] == mp[2][0]){
			if(mp[0][2] == 'O')f2=true;
			else if(mp[0][2] == 'X')f1=true;
		}
	if((f1&&cnt1 == cnt2) || (f2&&cnt1 == cnt2+1))cout << "No" << endl;
	else cout << "Yes" << endl;
}


int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		solve();
	}
	return 0;
}