当前位置：首页 > article >正文

蓝桥杯五子棋对弈

article 2025/2/27 5:45:18

五子棋对弈

问题描述

“在五子棋的对弈中，友谊的小船说翻就翻？” 不！对小蓝和小桥来说，五子棋不仅是棋盘上的较量，更是心与心之间的沟通。这两位挚友秉承着"友谊第一，比赛第二"的宗旨，决定在一块 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--;
    }
}