五子棋对弈

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

问题描述

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

比赛遵循以下规则：

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

在这一设定下，小蓝和小桥想知道，有多少种不同的棋局情况，既确保棋盘下满又保证比赛结果为平局。

答案提交

这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

运行限制

总通过次数: 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;
}