蓝桥杯五子棋对弈

五子棋对弈

问题描述

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

比赛遵循以下规则：

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

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

答案提交

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

c++代码

#include<bits/stdc++.h>using namespace std;class check {
public:int cur;int left;int up;int slash;int slash_fu;
};int white = 0, black = 0;
check chess[5][5];
int ans = 0;void dfs(int i, int j, int cur) {chess[i][j].left = 1;chess[i][j].up = 1;chess[i][j].slash = 1;chess[i][j].slash_fu = 1;if (j >= 1 && cur == chess[i][j - 1].cur) {if (chess[i][j - 1].left >= 4) return;chess[i][j].left = chess[i][j - 1].left + 1;}if (i >= 1 && cur == chess[i - 1][j].cur) {if (chess[i - 1][j].up >= 4) return;chess[i][j].up = chess[i - 1][j].up + 1;}if (i >= 1 && j >= 1 && cur == chess[i - 1][j - 1].cur) {if (chess[i - 1][j - 1].slash >= 4) return;chess[i][j].slash = chess[i - 1][j - 1].slash + 1;}if (i >= 1 && j + 1 <= 4 && cur == chess[i - 1][j + 1].cur) {if (chess[i - 1][j + 1].slash_fu >= 4) return;chess[i][j].slash_fu = chess[i - 1][j + 1].slash_fu + 1;}chess[i][j].cur = cur;if (i == 4 && j == 4) {ans++;return;}int x, y;x = i;y = j + 1;if (j == 4) {x = i + 1;y = 0;}if (white < 13) {white++;dfs(x, y, 0);white--;}if (black < 12) {black++;dfs(x, y, 1);black--;}
}int main() {/*white++;dfs(0, 0, 0);white--;black++;dfs(0, 0, 1);black--;cout << ans;*/cout << "3126376";return 0;
}//by wqs

题目解析

该问题是一个dfs深度搜索问题，不过要剪枝。

因为从左往右，从上往下填，所以可以不用考虑棋盘右边和下面的情况。

如果左边有四个和当前颜色相同直接return;

如果上边有四个和当前颜色相同直接return;

如果主对角线斜向上有四个和当前颜色相同直接return;

如果副对角线斜向上有四个和当前颜色相同直接return;

我当时还不记得考虑副对角线了，不知道算不算坑。

另外白子13个黑子12个，要判断黑子、白子数量是否大于0，再考虑下什么棋子。

代码实现

check类

class check {
public:int cur; //当前棋子的颜色，0表示白棋，1表示黑棋int left;//左边棋子连珠个数(连珠个数指的是连续颜色相同的棋子数量，包含自己)int up;//上边棋子连珠个数int slash;//主对角线棋子连珠个数int slash_fu;//副对角线棋子连珠个数
};
check chess[5][5];//模拟棋盘真实情况
//如果chess[i][j].cur == chess[i][j - 1].cur,chess[i][j].left = chess[i][j - 1].left + 1;
//如果我填入的这个棋子m的颜色和左边棋子n的颜色相同,m的左边棋子连珠数量=n的左边棋子连珠数量+1;
//如果chess[i][j].cur != chess[i][j - 1].cur,chess[i][j].left = 1;
//如果我填入的这个棋子m的颜色和左边棋子n的颜色不相同,m的左边棋子连珠数量=1;
//其他位置的动态转移方程自行推导。

dfs深度搜索

//在chess[i][j]填入cur
void dfs(int i, int j, int cur) {chess[i][j].left = 1;//初始化chess[i][j].up = 1;chess[i][j].slash = 1;chess[i][j].slash_fu = 1;if (j >= 1 && cur == chess[i][j - 1].cur) {if (chess[i][j - 1].left >= 4) return;//如果左边有四个和当前颜色相同直接return;chess[i][j].left = chess[i][j - 1].left + 1;}//检查左边if (i >= 1 && cur == chess[i - 1][j].cur) {if (chess[i - 1][j].up >= 4) return;//如果上边有四个和当前颜色相同直接return;chess[i][j].up = chess[i - 1][j].up + 1;}//检查上面if (i >= 1 && j >= 1 && cur == chess[i - 1][j - 1].cur) {if (chess[i - 1][j - 1].slash >= 4) return;//如果主对角线斜向上有四个和当前颜色相同直接return;chess[i][j].slash = chess[i - 1][j - 1].slash + 1;}//检查主对角线if (i >= 1 && j + 1 <= 4 && cur == chess[i - 1][j + 1].cur) {if (chess[i - 1][j + 1].slash_fu >= 4) return;//如果副对角线斜向上有四个和当前颜色相同直接return;chess[i][j].slash_fu = chess[i - 1][j + 1].slash_fu + 1;}//检查副对角线chess[i][j].cur = cur;//说明可以填入if (i == 4 && j == 4) {//说明棋盘填完了ans++;return;}int x, y;x = i;y = j + 1;//往右走if (j == 4) {x = i + 1;y = 0;//往下走}if (white < 13) {white++;dfs(x, y, 0);//下一个格子填白色white--;}if (black < 12) {black++;dfs(x, y, 1);//下一个格子填黑色black--;}
}