当前位置: 首页 > news >正文

蓝桥杯 五子棋对弈

五子棋对弈

问题描述

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

比赛遵循以下规则:

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

ans就是我们的答案

相关文章:

蓝桥杯 五子棋对弈

五子棋对弈 问题描述 “在五子棋的对弈中&#xff0c;友谊的小船说翻就翻&#xff1f;” 不&#xff01;对小蓝和小桥来说&#xff0c;五子棋不仅是棋盘上的较量&#xff0c;更是心与心之间的沟通。这两位挚友秉承着"友谊第一&#xff0c;比赛第二"的宗旨&#xff…...

【单片机】MSP430MSP432入门

文章目录 0 前言1 开发方式选择2 CCS和开发相关软件3 Keil开发MSP4324 IAR for 430开发MSP4305 总结 0 前言 最近因为想学DSP&#xff0c;所以把之前卸载的CCS给装回来了&#xff0c;手头也还有之前电赛剩下的MSP430和MSP432的板子&#xff0c;由于年代久远&#xff0c;想着花点…...

货车一键启动无钥匙进入手机远程启动的正确使用方法

一、移动管家货车无钥匙进入系统的使用方法 基本原理&#xff1a;无钥匙进入系统通常采用RFID无线射频技术和车辆身份识别码识别系统。车钥匙需要随身携带&#xff0c;当车钥匙靠近货车时&#xff0c;它会自动与货车的解码器匹配。开门操作&#xff1a;当靠近货车后&#xff0…...

自学c++之类、对象、封装

class 类名{int a;//属性 public://权限操作&#xff1b; } 1、权限 public(公共权限&#xff09;类内可以访问&#xff0c;类外可以访问protected&#xff08;保护权限&#xff09;类内可以访问&#xff0c;类外不可以访问&#xff08;儿子可以访问父亲中的保护内容&#xf…...

在VSCode中安装jupyter跑.ipynb格式文件

个人用vs用的较多&#xff0c;不习惯在浏览器单独打开jupyter&#xff0c;看着不舒服&#xff0c;直接上教程。 1、在你的环境中pip install ipykernel 2、在vscode的插件中安装jupyter扩展 3、安装扩展后&#xff0c;打开一个ipynb文件&#xff0c;并且在页面右上角配置内核 …...

SQL_优化

1 SQL优化 (1) 数据读取 ①分区裁剪:使用时只读取需要的分区. ②列裁剪:读取操作(select、where、join、group by、sort by等),不读取不需要的列,减少IO消耗. (2) 数据筛选 ①分区先过滤,区分度大的字段先过滤. ②不在筛选字段上使用函数和表达式. (3) 分组聚合 ①使用窗口函数…...

Neo4j使用neo4j-admin导入csv数据方法

在neo4j desktop里创建project&#xff0c;创建dbms&#xff0c;创建database。 将csv文件放入如下import路径中&#xff0c;然后就可以使用相对路径来使用csv了。 在neo4j desktop中打开Terminal 键入导入数据语句&#xff1a; neo4j-admin database import full --nodes&qu…...

Node.js 登录鉴权

目录 Session express-session 配置 express-session 函数 ts 要配置声明文件 express-session.d.ts express-session 使用 express-session 带角色 Token 什么是 JWT token jsonwebtoken 使用 jsonwebtoken 带角色 Session express 使用 express-session 管理会话&…...

内存泄漏指什么?常见的内存泄漏有哪些?

内存泄漏是指程序在运行过程中&#xff0c;由于某些原因导致程序无法释放已经不再使用的内存&#xff0c;使得这部分内存持续被占用&#xff0c;最终可能导致系统可用内存逐渐减少&#xff0c;严重时会影响系统性能甚至导致程序崩溃。&#xff08;内存泄漏是指程序中已经分配的…...

【PromptCoder】使用 package.json 生成 cursorrules

【PromptCoder】使用 package.json 生成 cursorrules 在当今快节奏的开发世界中&#xff0c;效率和准确性至关重要。开发者们不断寻找能够优化工作流程、帮助他们更快编写高质量代码的工具。Cursor 作为一款 AI 驱动的代码编辑器&#xff0c;正在彻底改变我们的编程方式。但如…...

STM32的C语言软件延时函数

STM32的延时方法很多&#xff0c;其中采用定时器延时&#xff0c;可以得到较为精确的延时&#xff0c;但是有时对延时精度要求不高的场合&#xff0c;采用软件延时&#xff0c;也是必须的。特别是在RTOS系统中&#xff0c;使用SysTick的普通计数模式对延迟进行管理&#xff0c;…...

【洛谷排序算法】P1012拼数-详细讲解

洛谷 P1012 拼数这道题本身并非单纯考察某种经典排序算法&#xff08;如冒泡排序、选择排序、插入排序、快速排序、归并排序等&#xff09;的实现&#xff0c;而是在排序的基础上&#xff0c;自定义了排序的比较规则&#xff0c;属于自定义排序类型的题目。不过它借助了标准库中…...

在WINDOWS系统使用CMake gui编译NLopt配合VSCode使用

1. 准备工作 安装CMake&#xff1a;从CMake官网下载并安装CMake。下载Nlopt源码&#xff1a;从Nlopt官网或GitHub仓库下载Nlopt源码。安装编译器&#xff1a;确保已安装Visual Studio或其他支持的编译器&#xff08;如MinGW&#xff09;。 2. 配置CMake 方式1 打开CMake GU…...

angular生命周期

ngOnChanges&#xff1a;当组件的输入属性&#xff08;Input&#xff09;发生变化时调用。 ngOnInit&#xff1a;在组件的输入属性初始化后调用&#xff0c;但此时视图尚未加载。 ngAfterContentInit&#xff1a;在组件的内容投影&#xff08;ng-content&#xff09;初始化后…...

[AI概念域] AI 大模型是如何被训练出来的?(通俗解读)

说明&#xff1a;这里使用 学生成长五部曲 比喻带你理解大模型如何从零开始学会思考。 AI大模型的训练过程可分为四个核心阶段&#xff1a; 首先进行海量数据收集与清洗&#xff0c;如同为“学生”准备涵盖各领域知识的教材库&#xff1b;接着通过预训练让模型完成“填空题”…...

Mellanox的LAG全称是什么?网卡的创建机制如何?(Link Aggregation Group 链路聚合组)

背景 对于双端口的网卡&#xff0c;有时候有将链路聚合的需求。在Mellanox网卡上通过LAG提供。对于RoCE的报文在Mellanox上也可以通过LAG来完成报文收发&#xff0c;叫做RoCE over LAG。但是仅仅适用于双端口卡。 关键点 LAG&#xff1a; Link Aggregation Group (LAG) 链路…...

【最大通过数——二分】

题目 代码 #include<bits/stdc.h> using namespace std; using ll long long;const int N 2e510;int n, m, k; ll a[N], b[N];bool check(int mid) {for(int i 0; i < mid; i){if(i > n) break;if(mid-i > m) continue;if(a[i] b[mid-i] < k) return tr…...

Liunx系统中FTP与NFS

目录 一、FTP文件传输协议 1.1、FTP工作原理 1.2、FTP状态码 1.3、FTP用户类型 1.4、FTP软件vsftpd 1.4.1、安装vsftpd 1.4.2、vsftpd配置文件 二、NFS网络文件系统 2.1、NFS工作原理 2.2、NFS软件 2.3、NFS共享配置文件格式 2.4、NFS相关命令 2.4.1、exportfs 2.…...

uniapp 测试 IPA 包安装到测试 iPhone

将uniapp测试IPA包安装到测试iPhone有以下几种方法&#xff1a; 使用Xcode安装 确保计算机上安装了Xcode&#xff0c;并将iOS设备通过数据线连接到计算机。打开Xcode&#xff0c;在菜单栏中选择Window->Devices and Simulators&#xff0c;在设备列表中找到要安装的iPhone…...

结构体指针传递给函数注意事项

在 C 语言中&#xff0c;传递结构体指针给函数是一种常见且高效的编程方式。不过&#xff0c;在实际操作时&#xff0c;有一些重要的注意事项需要留意&#xff0c;下面为你详细介绍&#xff1a; 1. 避免空指针引用 在函数内部使用结构体指针前&#xff0c;要先检查该指针是否为…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

[ACTF2020 新生赛]Include 1(php://filter伪协议)

题目 做法 启动靶机&#xff0c;点进去 点进去 查看URL&#xff0c;有 ?fileflag.php说明存在文件包含&#xff0c;原理是php://filter 协议 当它与包含函数结合时&#xff0c;php://filter流会被当作php文件执行。 用php://filter加编码&#xff0c;能让PHP把文件内容…...

安卓基础(Java 和 Gradle 版本)

1. 设置项目的 JDK 版本 方法1&#xff1a;通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分&#xff0c;设置 Gradle JDK 方法2&#xff1a;通过 Settings File → Settings... (或 CtrlAltS)…...