题目分析
问题描述
在一个5×5的棋盘上，小蓝（白棋）和小桥（黑棋）交替下棋，白棋先手。要求棋盘被填满时，双方均未形成五连珠，求满足条件的棋局数目。
关键条件
1. **棋盘填满**：白棋13个，黑棋12个。
2. **平局判定**：填满时，所有行、列、对角线均无连续五个同色棋子。
3. **下棋顺序**：必须严格交替，白棋先手。
---
解法思路
深度优先搜索（DFS）结合剪枝
通过DFS遍历所有可能的棋盘状态，在填满棋盘时检查是否满足平局条件。
- **递归状态**：当前已下棋子数（`sum`）、白棋数（`b`）、黑棋数（`h`）。
- **剪枝条件**：若某一步形成五连珠，立即终止该分支。
- **遍历顺序**：按棋盘格子顺序依次尝试放置白棋或黑棋，但需确保颜色数量合法。
代码实现
cpp
#include<bits/stdc++.h>
using namespace std;
//方法:搜索
//分解题目:条件1:棋盘被填满，得出白棋13个黑棋12个。更具平局条件，找到搜索算法的退出条件。
//递归条件:每个格子只有两种状态白和黑记作1和0，
//定义一个变量记录平局数量
int mp[5][5];
long long u=0;
void dfs(int sum,int b,int h)
{//更具分析先写框架即退出条件if(sum==25){//第一个要满足的条件，不符合return掉if(b==13&&h==12){//连续五个棋子一样跳出;for(int i=0;i<5;i++){int p=mp[i][0]+mp[i][1]+mp[i][2]+mp[i][3]+mp[i][4];if(p==0||p==5) return;int q=mp[0][i]+mp[1][i]+mp[2][i]+mp[3][i]+mp[4][i];if(q==0||q==5) return;}//判断对角线int s=mp[0][0]+mp[1][1]+mp[2][2]+mp[3][3]+mp[4][4];if(s==0||s==5) return;int f=mp[0][4]+mp[1][3]+mp[2][2]+mp[3][1]+mp[4][0];if(f==0||f==5) return;u++;}return;}//递归条件处理地图//对于坐标的处理，可以利用sum的值小技巧int x=sum/5;int y=sum%5;
//白棋先手mp[x][y]=1;dfs(sum+1,b+1,h);mp[x][y]=0;dfs(sum+1,b,h+1);
}
//
int main()
{dfs(0,0,0);cout<<u;
}代码解释
1. **棋盘表示**：使用二维数组 `mp` 存储棋盘状态
2. DFS递归：
-sum` 表示当前步数，决定当前玩家颜色（白棋为1，黑棋为0）。
- 按顺序遍历每个格子，放置当前颜色后检查是否形成五连珠。
3. **剪枝优化**：在每一步放置棋子后立即检查是否形成五连珠，若形成则终止该分支。
#include <bits/stdc++.h>
using namespace std;int mp[5][5]; // 棋盘状态，0为黑棋，1为白棋
long long result = 0;// 检查当前位置是否形成五连珠
bool check(int x, int y) {int color = mp[x][y];// 检查行int cnt = 1;for (int i = y-1; i >= 0 && mp[x][i] == color; i--) cnt++;for (int i = y+1; i < 5 && mp[x][i] == color; i++) cnt++;if (cnt >= 5) return false;// 检查列cnt = 1;for (int i = x-1; i >= 0 && mp[i][y] == color; i--) cnt++;for (int i = x+1; i < 5 && mp[i][y] == color; i++) cnt++;if (cnt >= 5) return false;// 检查主对角线cnt = 1;for (int i = x-1, j = y-1; i >= 0 && j >= 0 && mp[i][j] == color; i--, j--) cnt++;for (int i = x+1, j = y+1; i < 5 && j < 5 && mp[i][j] == color; i++, j++) cnt++;if (cnt >= 5) return false;// 检查副对角线cnt = 1;for (int i = x-1, j = y+1; i >= 0 && j < 5 && mp[i][j] == color; i--, j++) cnt++;for (int i = x+1, j = y-1; i < 5 && j >= 0 && mp[i][j] == color; i++, j--) cnt++;if (cnt >= 5) return false;return true;
}// DFS遍历
void dfs(int step) {if (step == 25) {// 白棋13个，黑棋12个且无五连珠result++;return;}int x = step / 5, y = step % 5;// 当前玩家颜色（白棋先手）int color = (step % 2 == 0) ? 1 : 0;// 尝试放置当前颜色mp[x][y] = color;if (check(x, y)) { // 剪枝：检查是否形成五连dfs(step + 1);}// 回溯mp[x][y] = -1;
}int main() {memset(mp, -1, sizeof(mp)); // 初始化为-1表示空dfs(0);cout << result << endl;return 0;
}
4. **结果统计**：当棋盘填满且未形成五连珠时，计数增加。
---
复杂度分析
- **时间复杂度**：最坏情况下为 $O(25!)$，但通过剪枝大幅减少实际遍历次数。
- **空间复杂度**：$O(25)$，递归深度为棋盘大小。
---
**总结**
本题通过DFS遍历所有合法的棋盘状态，结合剪枝优化确保每一步均符合五子棋规则。代码模拟了严格的交替下棋过程，并实时检查五连珠条件，确保结果正确。该解法直观体现了回溯算法的核心思想，适用于小规模棋盘问题的求解。
