当前位置: 首页 > 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;要先检查该指针是否为…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分&#xff1a; 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...