P10386 [蓝桥杯 2024 省 A] 五子棋对弈题解复盘
![P10386 [蓝桥杯 2024 省 A] 五子棋对弈题解复盘](http://pic.xiahunao.cn/yaotu/P10386 [蓝桥杯 2024 省 A] 五子棋对弈题解复盘)
五子棋平局（蓝桥杯填空题）题解复盘
基本信息
| 项目 | 内容 |
|---|---|
| 题目编号、来源 | 蓝桥杯 五子棋平局（结果填空题） |
| 训练层级 | B DFS + 回溯 |
| 知识版块 | DFS、回溯、棋盘枚举、状态压缩 |
解题前・关键信号识别
| 维度 | 分析 |
|---|---|
| 目标、约束、底层结构 | 目标：5×5 棋盘，白棋先手共 13 个，黑棋 12 个，终局无人五子连珠，求平局终局数量；约束：棋盘 25 格，每格三种状态（空/白/黑），但终局无空格；底层结构：DFS 枚举 25 个格子的黑白状态，回溯恢复棋盘，剪枝限制棋子数量。 |
| 数据规模 | 25 个格子，每个格子 2 种状态（白/黑），总终局数 C(25,13) = 5,200,300，DFS 枚举所有方案完全可行。 |
| 候选算法和依据 | DFS + 回溯；依据：每个格子只有白/黑两种终局状态，按顺序逐格枚举，用剪枝减少搜索量。 |
| 复杂度预判 | 时间复杂度 O(2^25)，但剪枝后大幅减少；空间复杂度 O(25)。 |
解题后・外化复盘
| 维度 | 内容 |
|---|---|
| 实现结构 / 核心思路 | 第一步从 (0,0) 开始 DFS，逐格处理每个格子放白棋或黑棋；第二步每步检查白棋是否超过 13 个、黑棋是否超过 12 个，超过则剪枝返回；第三步当 25 个格子全部处理完（x==5），检查白棋是否恰好 13 个、黑棋恰好 12 个，且无人五子连珠，满足则 ans++；第四步定义 check() 函数检查 5 行、5 列、2 条对角线是否有五个相同棋子；第五步输出 ans。核心思想：枚举所有终局状态，筛选满足棋子数量且无人获胜的平局局面。 |
| 错因回溯 | 1. 剪枝条件放在出口后面，导致白棋超过 13 个的非法状态也被计入 ans；2. 出口处没有检查white == 13 && black == 12，导致棋子数量不对的终局也被计入；3. check() 函数用return true表示有人赢，调用时用!check()表示平局，逻辑正确但容易混淆；4. 忘记回溯恢复board[x][y] = 0，导致棋盘状态被污染。 |
| 边界和易错点 | 1. 剪枝条件 `if (white > 13 |
| 下次看到什么信号，我应该想到这个方法 | 看到「棋盘 + 黑白棋子 + 平局 + 结果填空」，用 DFS 枚举所有终局状态 + 回溯。 |
AC 完整代码
#include<iostream>usingnamespacestd;intboard[5][5];intans=0;boolcheck(){for(inti=0;i<5;i++){if(board[i][0]!=0&&board[i][0]==board[i][1]&&board[i][1]==board[i][2]&&board[i][2]==board[i][3]&&board[i][3]==board[i][4]){returntrue;}if(board[0][i]!=0&&board[0][i]==board[1][i]&&board[1][i]==board[2][i]&&board[2][i]==board[3][i]&&board[3][i]==board[4][i]){returntrue;}}if(board[0][0]!=0&&board[0][0]==board[1][1]&&board[1][1]==board[2][2]&&board[2][2]==board[3][3]&&board[3][3]==board[4][4]){returntrue;}if(board[0][4]!=0&&board[0][4]==board[1][3]&&board[1][3]==board[2][2]&&board[2][2]==board[3][1]&&board[3][1]==board[4][0]){returntrue;}returnfalse;}voiddfs(intx,inty,intwhite,intblack){if(white>13||black>12)return;if(x==5){if(white==13&&black==12&&!check())ans++;return;}intnx=x,ny=y+1;if(ny==5){nx=x+1;ny=0;}board[x][y]=1;dfs(nx,ny,white+1,black);board[x][y]=2;dfs(nx,ny,white,black+1);board[x][y]=0;}intmain(){dfs(0,0,0,0);cout<<ans<<endl;return0;}