安徽省小学组2023第4题：海克斯（hex）

今年考省赛的时候还没学搜索，这题是个可爱的鸭蛋 [ 哭 ]

暑假想报仇一下，本来以为很简单，但80%就很难受，调了好久

题目有点长嘿嘿嘿

题目描述 Description

为了写作业，小可可和小多在下一种奇怪的棋——hex棋。
问题描述：这种棋盘规则如下：
棋盘由N*N个六边形格子构成。
称两个格子相连通，当且仅当两个格子对应的六边形共边。
将从上往下第 i 行从左到右第 j 个格子称为 (i, j)。对于一个不在边界上的格子 (i, j)，它和 (i, j + 1),(i, j − 1),(i + 1, j),(i + 1, j − 1),(i − 1, j),(i − 1, j + 1) 这些格子相 连通，而边界上的格子只与上述格子中存在的格子相连通。 两人轮流下棋，小可可先手，小可可每次选一个空的格子下一个红色棋子，小多每 次选一个空的格子下一个蓝色棋子，如果小可可将上下两条边界用红色棋子连通了，那 么小可可胜；如果小多将左右两条边界用蓝色棋子连通了，那么小多胜。 接下来给出若干个局面，请你判断每一局是小可可胜，还是小多胜，还是目前没有 人获得胜利（容易证明，不可能两人都达到获胜条件）。

输入描述 Input Description

第一行一个正整数 T，代表他们下了 T 盘棋。
对于每一盘棋：
输入一行一个正整数 N，代表目前这盘棋的棋盘的大小。
之后 N 行，每行 N 个 −1, 0, 1 中的整数，第 i 行的第 j 个整数代表格子 (i, j) 的
状态，如果为 −1 则该格子中为蓝色棋子，如果为 0 则该格子为空，如果为 1 则该格子
中为红色棋子。

输出描述 Output Description

输出共 T 行，请对于每个局面，输出一行一个字符串：如果小可可胜，则输出 ke；
如果小多胜，则输出 do；如果目前两人都还未获胜，则输出 yet。

样例输入 Sample Input

3 4 0 1 0 -1 0 -1 1 0 -1 -1 1 0 0 0 1 0 4 0 1 1 -1 0 -1 1 0 -1 -1 1 0 0 0 1 0 4 0 1 -1 -1 0 -1 1 1 -1 -1 1 0 0 0 1 0

样例输出 Sample Output

yet ke do

数据范围及提示 Data Size & Hint

【样例解释】
在第一个棋盘中，不存在将上下边界连通的红色棋子序列，也不存在将左右边界连
通的蓝色棋子序列，故目前未分出胜负。
在第二个棋盘中，上下两个边界由 (1, 3),(2, 3),(3, 3),(4, 3) 这些红色棋子连通了，所
以小可可获胜了。
在第三个棋盘中，左右两个边界由 (3, 1),(2, 2),(1, 3),(1, 4) 这些蓝色棋子连通了，所
以小多获胜了。
【数据范围】
对于 20% 的数据，满足 1 ≤ N ≤ 3。
对于另外 40% 的数据，满足给出的棋局已经分出胜负。
对于 100% 的数据，满足 1 ≤ T ≤ 10，1 ≤ N ≤ 100。

基本搜索得会（迷宫），不会的自觉离开，可以带个代码走人

我们会发现这题和迷宫很像，思想也差不多，但这个要有两个dfs函数，因为小可可和小多都要判断一次。和迷宫的区别就是：迷宫是判断这个点能不能走，这题是判断是否使我们想要的颜色。

此外两个题的共同点都是要判断这条路有没有走过。

会迷宫的应该都看得懂吧，看不懂的直接抄食不食

#include<bits/stdc++.h>
using namespace std;
int dx[6]={0,0,1,1,-1,-1};
int dy[6]={1,-1,0,-1,0,1};
bool f[105][105];
int a[105][105],n;
bool flag; 
void dfsr(int x,int y){
	if(a[x][y]!=1) return ;
    if(x==n){
        if(a[x][y]==1) flag = 1;
        return ;
    }
	for(int i=0;i<6;i++){
		if(flag==1) break;
		x = x+dx[i];y = y+dy[i];
		if(f[x][y]==0&&a[x][y]==1&&x>=1&&x<=n&&y>=1&&y<=n){
			f[x][y] = 1;
			dfsr(x,y);
		}
		x = x-dx[i];y = y-dy[i];
	}
}
void dfsb(int x,int y){
	if(a[x][y]!=-1) return ;
    if(y==n){
        if(a[x][y]==-1) flag = 1;
        return ;
    }
	for(int i=0;i<6;i++){
		if(flag==1) break;
		x = x+dx[i];y = y+dy[i];
		if(f[x][y]==0&&a[x][y]==-1){
			f[x][y] = 1;
			dfsb(x,y);
		}
		x = x-dx[i];y = y-dy[i];
	}
}
int main()
{
	int t; 
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				scanf("%d",&a[i][j]);
			}
		}
		flag = 0;
		memset(f,0,sizeof(f));
		for(int i=1;i<=n;i++){
			dfsr(1,i);
			if(flag==1){
				cout<<"ke"<<endl;
				break;
			}
		}
		if(flag==1) continue;
		memset(f,0,sizeof(f));
			for(int i=1;i<=n;i++){
				dfsb(i,1);
				if(flag==1){
					cout<<"do"<<endl; 
					break;
				}
			}
		if(flag==0) cout<<"yet"<<endl;
	}
	return 0;
}

代码有点长……

作者有话说：

家人们谁懂啊：为什么别人随便发点就有两位数的点赞，我唯一的点赞还是自己点的。复制完代码点个免费的赞和关注吧，想要什么题的代码在评论区里说，我流量不多，留言的我都会回。美女帅哥们，可怜可怜我这个小学生吧。