题解：P10386 [蓝桥杯 2024 省 A] 五子棋对弈

P10386 [蓝桥杯 2024 省 A] 五子棋对弈题解

思路

计划分为两步

直接暴力DFS出所有棋局的情况
检查有没有人赢，没有就计数++

第一步

先用两个变量

w,b

记录白/黑子的剩余数量，每层搜索分别判断有无白/黑子，有就在相应的位置落子并继续搜索。

重点

~~虽然搜索直接用 $x,y$ 表示搜索的位置更方便，但我还是选择用只一个 $p$ 。~~ 所以如何把这个

p

转换为

x,y

就是问题所在。上公式：

x=(p-1) \div 5+1,y=(p-1) \bmod 5+1

。如果你习惯

x,y

下标从

0

开始，这是公式：

x=(p-1) \div 5,y=(p-1) \bmod 5

。

第二步

for循环从

1

到

5

，分别检查第

i

行/列是否全是白/黑子。对于对角线，我会给出通用的公式。左上-右下：

y=x (1 \le x \le n)

，右上-左下：

y=n+1-x (1 \le x \le n)

。这样检查两条对角线是否全是白/黑子。

代码

CPP

#include <bits/stdc++.h>
using namespace std;
int mapp[10][10];//棋盘
int w=13,b=12;//白黑子剩余数量
int cnt;//计数
void check(){
	for (int i=1;i<=5;i++){//检查第i行/列
		if (mapp[i][1]&&mapp[i][2]&&mapp[i][3]&&mapp[i][4]&&mapp[i][5]) return ;//第i行全白
		if (!mapp[i][1]&&!mapp[i][2]&&!mapp[i][3]&&!mapp[i][4]&&!mapp[i][5]) return ;//第i行全黑
		if (mapp[1][i]&&mapp[2][i]&&mapp[3][i]&&mapp[4][i]&&mapp[5][i]) return ;//第i列全白
		if (!mapp[1][i]&&!mapp[2][i]&&!mapp[3][i]&&!mapp[4][i]&&!mapp[5][i]) return ;//第i列全黑
	}
	if (mapp[1][1]&&mapp[2][2]&&mapp[3][3]&&mapp[4][4]&&mapp[5][5]) return ;//左上-右下对角线全白
	if (!mapp[1][1]&&!mapp[2][2]&&!mapp[3][3]&&!mapp[4][4]&&!mapp[5][5]) return ;//左上-右下对角线全黑
	if (mapp[1][5]&&mapp[2][4]&&mapp[3][3]&&mapp[4][2]&&mapp[5][1]) return ;//右上-左下对角线全白
	if (!mapp[1][5]&&!mapp[2][4]&&!mapp[3][3]&&!mapp[4][2]&&!mapp[5][1]) return ;//右上-左下对角线全黑
	cnt++;//经过天衣无缝的检查后，这个棋局可以判定为和棋了
}
void dfs(int p){//搜索到第p位
	if (p==26){//5*5填完了
		check();//检查
	}
	//白棋
	if (w){//如果还有白棋
		w--;//白棋子数量--
		//好好看，好好学，搜索位数转坐标
		mapp[(p-1)/5+1][(p-1)%5+1]=1;//棋盘标记为白子
		dfs(p+1);//搜索下一个点位
		//回溯不用改棋盘，下次搜到这一位自然会改
		w++;//回溯
	}
	//黑棋
	if (b){
		b--;
		mapp[(p-1)/5+1][(p-1)%5+1]=0;
		dfs(p+1);
		b++;
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	dfs(1);//从第1位开始搜
	cout<<cnt;//输出答案
	return 0;
}

小技巧

该说还是得说，既然这题固定输出：

CPP

#include <bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout<<3126376;
	return 0;
}

题解：P10386 [蓝桥杯 2024 省 A] 五子棋对弈

文章操作

P10386 [蓝桥杯 2024 省 A] 五子棋对弈题解

思路

第一步

重点

第二步

代码

小技巧

相关推荐

评论

题解：P10386 [蓝桥杯 2024 省 A] 五子棋对弈