蓝桥杯 五子棋对弈
五子棋对弈
问题描述
“在五子棋的对弈中,友谊的小船说翻就翻?” 不!对小蓝和小桥来说,五子棋不仅是棋盘上的较量,更是心与心之间的沟通。这两位挚友秉承着"友谊第一,比赛第二"的宗旨,决定在一块 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--;}
}
ans就是我们的答案
相关文章:
蓝桥杯 五子棋对弈
五子棋对弈 问题描述 “在五子棋的对弈中,友谊的小船说翻就翻?” 不!对小蓝和小桥来说,五子棋不仅是棋盘上的较量,更是心与心之间的沟通。这两位挚友秉承着"友谊第一,比赛第二"的宗旨ÿ…...
【单片机】MSP430MSP432入门
文章目录 0 前言1 开发方式选择2 CCS和开发相关软件3 Keil开发MSP4324 IAR for 430开发MSP4305 总结 0 前言 最近因为想学DSP,所以把之前卸载的CCS给装回来了,手头也还有之前电赛剩下的MSP430和MSP432的板子,由于年代久远,想着花点…...
货车一键启动无钥匙进入手机远程启动的正确使用方法
一、移动管家货车无钥匙进入系统的使用方法 基本原理:无钥匙进入系统通常采用RFID无线射频技术和车辆身份识别码识别系统。车钥匙需要随身携带,当车钥匙靠近货车时,它会自动与货车的解码器匹配。开门操作:当靠近货车后࿰…...
自学c++之类、对象、封装
class 类名{int a;//属性 public://权限操作; } 1、权限 public(公共权限)类内可以访问,类外可以访问protected(保护权限)类内可以访问,类外不可以访问(儿子可以访问父亲中的保护内容…...
在VSCode中安装jupyter跑.ipynb格式文件
个人用vs用的较多,不习惯在浏览器单独打开jupyter,看着不舒服,直接上教程。 1、在你的环境中pip install ipykernel 2、在vscode的插件中安装jupyter扩展 3、安装扩展后,打开一个ipynb文件,并且在页面右上角配置内核 …...
SQL_优化
1 SQL优化 (1) 数据读取 ①分区裁剪:使用时只读取需要的分区. ②列裁剪:读取操作(select、where、join、group by、sort by等),不读取不需要的列,减少IO消耗. (2) 数据筛选 ①分区先过滤,区分度大的字段先过滤. ②不在筛选字段上使用函数和表达式. (3) 分组聚合 ①使用窗口函数…...
Neo4j使用neo4j-admin导入csv数据方法
在neo4j desktop里创建project,创建dbms,创建database。 将csv文件放入如下import路径中,然后就可以使用相对路径来使用csv了。 在neo4j desktop中打开Terminal 键入导入数据语句: 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 管理会话&…...
内存泄漏指什么?常见的内存泄漏有哪些?
内存泄漏是指程序在运行过程中,由于某些原因导致程序无法释放已经不再使用的内存,使得这部分内存持续被占用,最终可能导致系统可用内存逐渐减少,严重时会影响系统性能甚至导致程序崩溃。(内存泄漏是指程序中已经分配的…...
【PromptCoder】使用 package.json 生成 cursorrules
【PromptCoder】使用 package.json 生成 cursorrules 在当今快节奏的开发世界中,效率和准确性至关重要。开发者们不断寻找能够优化工作流程、帮助他们更快编写高质量代码的工具。Cursor 作为一款 AI 驱动的代码编辑器,正在彻底改变我们的编程方式。但如…...
STM32的C语言软件延时函数
STM32的延时方法很多,其中采用定时器延时,可以得到较为精确的延时,但是有时对延时精度要求不高的场合,采用软件延时,也是必须的。特别是在RTOS系统中,使用SysTick的普通计数模式对延迟进行管理,…...
【洛谷排序算法】P1012拼数-详细讲解
洛谷 P1012 拼数这道题本身并非单纯考察某种经典排序算法(如冒泡排序、选择排序、插入排序、快速排序、归并排序等)的实现,而是在排序的基础上,自定义了排序的比较规则,属于自定义排序类型的题目。不过它借助了标准库中…...
在WINDOWS系统使用CMake gui编译NLopt配合VSCode使用
1. 准备工作 安装CMake:从CMake官网下载并安装CMake。下载Nlopt源码:从Nlopt官网或GitHub仓库下载Nlopt源码。安装编译器:确保已安装Visual Studio或其他支持的编译器(如MinGW)。 2. 配置CMake 方式1 打开CMake GU…...
angular生命周期
ngOnChanges:当组件的输入属性(Input)发生变化时调用。 ngOnInit:在组件的输入属性初始化后调用,但此时视图尚未加载。 ngAfterContentInit:在组件的内容投影(ng-content)初始化后…...
[AI概念域] AI 大模型是如何被训练出来的?(通俗解读)
说明:这里使用 学生成长五部曲 比喻带你理解大模型如何从零开始学会思考。 AI大模型的训练过程可分为四个核心阶段: 首先进行海量数据收集与清洗,如同为“学生”准备涵盖各领域知识的教材库;接着通过预训练让模型完成“填空题”…...
Mellanox的LAG全称是什么?网卡的创建机制如何?(Link Aggregation Group 链路聚合组)
背景 对于双端口的网卡,有时候有将链路聚合的需求。在Mellanox网卡上通过LAG提供。对于RoCE的报文在Mellanox上也可以通过LAG来完成报文收发,叫做RoCE over LAG。但是仅仅适用于双端口卡。 关键点 LAG: 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有以下几种方法: 使用Xcode安装 确保计算机上安装了Xcode,并将iOS设备通过数据线连接到计算机。打开Xcode,在菜单栏中选择Window->Devices and Simulators,在设备列表中找到要安装的iPhone…...
结构体指针传递给函数注意事项
在 C 语言中,传递结构体指针给函数是一种常见且高效的编程方式。不过,在实际操作时,有一些重要的注意事项需要留意,下面为你详细介绍: 1. 避免空指针引用 在函数内部使用结构体指针前,要先检查该指针是否为…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
Java 二维码
Java 二维码 **技术:**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习) 一、Aspose.PDF 简介二、说明(⚠️仅供学习与研究使用)三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...
宇树科技,改名了!
提到国内具身智能和机器人领域的代表企业,那宇树科技(Unitree)必须名列其榜。 最近,宇树科技的一项新变动消息在业界引发了不少关注和讨论,即: 宇树向其合作伙伴发布了一封公司名称变更函称,因…...
Oracle11g安装包
Oracle 11g安装包 适用于windows系统,64位 下载路径 oracle 11g 安装包...
