五子棋对弈

1.五子棋对弈 - 蓝桥云课

问题描述

“在五子棋的对弈中，友谊的小船说翻就翻？”不！对小蓝和小桥来说，五子棋不仅是棋盘上的较量，更是心与心之间的沟通。这两位挚友秉承着“友谊第一，比赛第二”的宗旨，决定在一块5×5的棋盘上，用黑白两色的棋子来决出胜负。但他们又都不忍心让对方失落，于是决定用一场和棋（平局）作为彼此友谊的见证。

比赛遵循以下规则：

1. ​棋盘规模：比赛在一个5×5的方格棋盘上进行，共有25个格子供下棋使用。
2. ​棋子类型：两种棋子，黑棋与白棋，代表双方，小蓝持白棋，小桥持黑棋。
3. ​先手规则：白棋（小蓝）具有先手优势，即在棋盘空白时率先落子（下棋）。
4. ​轮流落子：玩家们交替在棋盘上放置各自的棋子，每次仅放置一枚。
5. ​胜利条件：率先在横线、竖线或斜线上形成连续的五个同色棋子的一方获胜。
6. ​平局条件：当所有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;
}