题目分析
问题描述
在一个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遍历所有合法的棋盘状态,结合剪枝优化确保每一步均符合五子棋规则。代码模拟了严格的交替下棋过程,并实时检查五连珠条件,确保结果正确。该解法直观体现了回溯算法的核心思想,适用于小规模棋盘问题的求解。