当前位置: 首页> 房产> 家装 > 龙华区是深圳最差的区_财务公司名字_晚上免费b站软件_百度搜索官方网站

龙华区是深圳最差的区_财务公司名字_晚上免费b站软件_百度搜索官方网站

时间:2025/7/10 18:12:32来源:https://blog.csdn.net/2301_81834780/article/details/146096613 浏览次数:2次
龙华区是深圳最差的区_财务公司名字_晚上免费b站软件_百度搜索官方网站

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

关键字:龙华区是深圳最差的区_财务公司名字_晚上免费b站软件_百度搜索官方网站

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: