1.五子棋对弈 - 蓝桥云课
问题描述
“在五子棋的对弈中，友谊的小船说翻就翻？”不！对小蓝和小桥来说，五子棋不仅是棋盘上的较量，更是心与心之间的沟通。这两位挚友秉承着“友谊第一，比赛第二”的宗旨，决定在一块5×5的棋盘上，用黑白两色的棋子来决出胜负。但他们又都不忍心让对方失落，于是决定用一场和棋（平局）作为彼此友谊的见证。
比赛遵循以下规则：
- 棋盘规模：比赛在一个5×5的方格棋盘上进行，共有25个格子供下棋使用。
- 棋子类型：两种棋子，黑棋与白棋，代表双方，小蓝持白棋，小桥持黑棋。
- 先手规则：白棋（小蓝）具有先手优势，即在棋盘空白时率先落子（下棋）。
- 轮流落子：玩家们交替在棋盘上放置各自的棋子，每次仅放置一枚。
- 胜利条件：率先在横线、竖线或斜线上形成连续的五个同色棋子的一方获胜。
- 平局条件：当所有25个棋格都被下满棋子，而未决出胜负时，游戏以平局告终。
在这一设定下，小蓝和小桥想知道，有多少种不同的棋局情况，既确保棋盘下满又保证比赛结果为平局。
答案提交
这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 256M |
| C | 1s | 256M |
| Java | 3s | 512M |
| Python3 | 10s | 512M |
| PyPy3 | 3s | 512M |
| Go | 5s | 512M |
| JavaScript | 5s | 512M |
总通过次数: 1477 | 总提交次数: 2630 | 通过率: 56.2%
难度: 中等 标签: 模拟, 暴力, 省赛, DFS, 2024
版权声明
思路：
暴力
代码如下：
#include<iostream>
#include<algorithm>
using namespace std;
int arr[5][5];
int ans = 0;
void dfs(int cnt,int w,int b)
{if(cnt == 25) {if( w == 13 && b == 12){for(int i = 0 ; i < 5 ; i++)//行 {int sum = arr[i][0] + arr[i][1] + arr[i][2] + arr[i][3] + arr[i][4];if(sum == 0 || sum == 5)return;}for(int i = 0 ; i < 5 ; i++)//列 {int sum = arr[0][i] + arr[1][i] + arr[2][i] + arr[3][i] + arr[4][i];if(sum == 5 || sum == 0)return;}//正对角线int pd = arr[0][4] + arr[1][3] + arr[2][2] + arr[3][1] + arr[4][0];if(pd == 5 || pd == 0)return;//负对角线 int nd = arr[0][0] + arr[1][1] + arr[2][2] + arr[3][3] + arr[4][4];if(nd == 5 || nd == 0)return;ans++; }return; }int x = cnt / 5;int y = cnt % 5;//放白色 arr[x][y] = 1;dfs(cnt+1,w+1,b);//放黑色arr[x][y] = 0;dfs(cnt+1,w,b+1);
}
int main()
{dfs(0,0,0);//填入棋子的个数，白色white，黑色 black cout << ans;return 0;
}思路：
优化
代码如下：
#include<iostream>
#include<algorithm>
using namespace std;
int row[10];//行
int list[10];//列
int pd[10];//正对角线
int nd[10];//负对角线
int ans = 0;
void dfs(int x,int y,int cnt)
{if(y > 5){x++;y = 1;}if(x > 5){if(cnt == 12) {bool found = true; for(int i = 1 ; i <= 5 ; i++)//行{if(row[i] == 5 || row[i] == 0 || list[i] == 5 || list[i] == 0){found = false;break;}} if(pd[5] == 0 || pd[5] == 5 || nd[5] == 0 || nd[5] == 5)//主/副对角线 {found = false;}if(found)ans++;}return;}//该格子不放dfs(x,y+1,cnt);//该格子放row[x]++;list[y]++;pd[x+y-1]++;nd[x-y+5]++;dfs(x,y+1,cnt+1); row[x]--;list[y]--;pd[x+y-1]--;nd[x-y+5]--;
}
int main()
{dfs(1,1,0);//参数为x,y,填入白色棋子个数 (下标为0) cout << ans;return 0;
}
