洛谷P1312 [NOIP 2011 提高组] Mayan 游戏
题目
#算法/进阶搜索
思路:
根据题意,我们可以知道,这题只能枚举,剪枝,因此,我们考虑如何枚举,剪枝.
首先,我们要定义下降函数down(),使得小木块右移时,能够下降到最低处,其次,我们还需要写出判断函数,判断矩阵内是否有小木块没被消除.另外,我们还需要消除函数,将矩阵内三个相连的小木块清除,dfs()函数进行搜索
这里,我们定义数组横坐标代表原矩阵的列,纵坐标代表原矩阵的行,坐标轴从1,1开始
check判断函数:
直接判断当前矩阵中是否仍存在小正方行
bool check(){for(int i=1;i<=5;i++){for(int j=1;j<=7;j++){if(dp[i][j])return false;}}return true;}
clear()清除函数
由于我们后序每次将正方行下降后都需要判断当前是否需要清除,所以我们将clear定义为int,
判断的时候,我们三个一组的判断
1.先横向判断每一行是否有三个连续的
2.在竖向判断是否有三个连续的
注意:这里我们全部判断完后再进行删除,否则会出现4-5个连续的同色方块只能删除三个
int clear(){int g=0;int del[10][10]={0};
横向删除for(int i=1;i<=5;i++){for(int j=1;j<=7;j++){if(!dp[i][j])continue;if(i>1&&i<5){if(dp[i-1][j]==dp[i][j]&&dp[i][j]==dp[i+1][j]){del[i-1][j]=del[i][j]=del[i+1][j]=g=1;}}}}
竖向删除for(int i=1;i<=5;i++){for(int j=2;j<=6;j++){if(dp[i][j]==0)continue;if(dp[i][j-1]==dp[i][j]&&dp[i][j]==dp[i][j+1]){del[i][j-1]=del[i][j]=del[i][j+1]=g=1;}}}for(int i=1;i<=5;i++){for(int j=1;j<=7;j++){if(del[i][j]==1)dp[i][j]=0;}}return g;}
down()下降函数
在下降的时候,会出现一列的小正方形多组不连续,比如1020201,我们在下降的时候需要先将第一个2下降到最底部,再将第二个2下降到最底部,最后将1下降到最底部,所以,我们从下往上降
void down(){for(int i=1;i<=5;i++){
从原矩阵第二行开始下降for(int j=2;j<=7;j++){if(dp[i][j]==0)continue;int k=j;这里一定要添加限定条件k-1>=1while(k-1>=1&&dp[i][k-1]==0){swap(dp[i][k],dp[i][k-1]);k--;}}}}
dfs()函数
定义flag代表我们是否找到可删除合法方案
void dfs(int x){
如果已经删除完了,直接返回if(flag)return;if(x>n){if(check()){for(int i=1;i<=n;i++){
res,0放原坐标轴x,1放原坐标y,2放正方向移动方向cout<<res[i][0]<<' '<<res[i][1]<<' '<<res[i][2]<<endl;}flag=true;}return;}for(int i=1;i<=5;i++){for(int j=1;j<=7;j++){if(dp[i][j]==0)continue;int tmp[10][10];
保存初始状态memcpy(tmp,dp,sizeof(tmp));
正方行右移if(i<5){res[x][0]=i-1;res[x][1]=j-1;res[x][2]=1;swap(dp[i][j],dp[i+1][j]);for(down();clear()!=0;down());dfs(x+1);
恢复初始状态memcpy(dp,tmp,sizeof(dp));}
正方向左移if(i>=2){res[x][0]=i-1;res[x][1]=j-1;res[x][2]=-1;swap(dp[i][j],dp[i-1][j]);for(down();clear()!=0;down());dfs(x+1);
恢复初始状态memcpy(dp,tmp,sizeof(dp));}}}}
完整代码
#include<iostream>#include<cstring>using namespace std;int n;int dp[10][10];int res[30][3];bool flag=false;bool check(){for(int i=1;i<=5;i++){for(int j=1;j<=7;j++){if(dp[i][j])return false;}}return true;}int clear(){int g=0;int del[10][10]={0};for(int i=1;i<=5;i++){for(int j=1;j<=7;j++){if(!dp[i][j])continue;if(i>1&&i<5){if(dp[i-1][j]==dp[i][j]&&dp[i][j]==dp[i+1][j]){del[i-1][j]=del[i][j]=del[i+1][j]=g=1;}}}}for(int i=1;i<=5;i++){for(int j=2;j<=6;j++){if(dp[i][j]==0)continue;if(dp[i][j-1]==dp[i][j]&&dp[i][j]==dp[i][j+1]){del[i][j-1]=del[i][j]=del[i][j+1]=g=1;}}}for(int i=1;i<=5;i++){for(int j=1;j<=7;j++){if(del[i][j]==1)dp[i][j]=0;}}return g;}void down(){for(int i=1;i<=5;i++){for(int j=2;j<=7;j++){if(dp[i][j]==0)continue;int k=j;while(k-1>=1&&dp[i][k-1]==0){swap(dp[i][k],dp[i][k-1]);k--;}}}}void dfs(int x){if(flag)return;if(x>n){if(check()){for(int i=1;i<=n;i++){cout<<res[i][0]<<' '<<res[i][1]<<' '<<res[i][2]<<endl;}flag=true;}return;}for(int i=1;i<=5;i++){for(int j=1;j<=7;j++){if(dp[i][j]==0)continue;int tmp[10][10];memcpy(tmp,dp,sizeof(tmp));if(i<5){res[x][0]=i-1;res[x][1]=j-1;res[x][2]=1;swap(dp[i][j],dp[i+1][j]);for(down();clear()!=0;down());dfs(x+1);memcpy(dp,tmp,sizeof(dp));}if(i>=2){res[x][0]=i-1;res[x][1]=j-1;res[x][2]=-1;swap(dp[i][j],dp[i-1][j]);for(down();clear()!=0;down());dfs(x+1);memcpy(dp,tmp,sizeof(dp));}}}}int main(void){cin>>n;for(int i=1;i<=5;i++){int cnt=1;int tmp;while(cin>>tmp&&tmp){dp[i][cnt]=tmp;cnt++;}}dfs(1);if(flag==false){cout<<-1<<endl;}return 0;}
相关文章：
洛谷P1312 [NOIP 2011 提高组] Mayan 游戏
题目 #算法/进阶搜索 思路: 根据题意,我们可以知道,这题只能枚举,剪枝,因此,我们考虑如何枚举,剪枝. 首先,我们要定义下降函数down(),使得小木块右移时,能够下降到最低处,其次,我们还需要写出判断函数,判断矩阵内是否有小木块没被消除.另外,我们还需要消除函数,将矩阵内三个相连…...
)
c++ (异常)
1.异常的概念及使用 1.1异常的概念 异常处理机制允许程序中独立开发的部分能够在运行时就出现的问题进行通信并做出相应的处理， 异常使得我们能够将问题的检测与解决问题的过程分开，程序的一部分负责检测问题的出现，然后 解决问题的任务传…...
MySQL如何实现行行比较
概述 在MySQL中实现行行比较通常涉及比较同一表或不同表中不同行的数据。以下是几种常见的方法及示例： 1. 自连接（Self-Join） 通过将表与自身连接，比较不同行的数据。 场景示例：比较同一用户相邻订单的金额差异。 …...
springboot2.X创建maven多模块工程
因为需要，所以付出。 好长时间没有搭建新的框架了，最近在搭建微服务的多模块maven工程，现在就将创建的过程记录下来，方便自学的小伙伴找寻资料，少走弯路。好了下面直接开干。 开发工具 ：idea 、springboo…...
)
八股文---Redis(1)
目录 1.Redis-使用场景 1.我看你做的项目中，都用到了redis，你在最近的项目中哪些场景使用了redis呢？ 2.缓存三兄弟可以我看我另一个文章（穿透，雪崩，击穿） 3.redis做为缓存，mysql…...
QT聊天项目DAY06
1.从git上同步项目 编译测试，编译通过 Post请求测试 测试成功 2. email is 打印有问题，检查 解析结果是存储在jsonResult中的，修改 3. 客户端实现Post验证码请求 3.1 同步Qt客户端项目 检查QT版本，由于我在公司用的还是QT5.12.9…...
python（八）-数据类型转换
#数据类型转换 #转换为整型int #字符串str--》整数int #纯数字的字符串可以转换，否则会报错 s 2025 n int(s) print(type(s),type(n)) print(n)#浮点数float--》整数int s1 2.23 print(int(s1))#bool-->整数int s2,s3 True,False print(int(s2),int(s3))#转…...
JavaScript 变量命名规范
在编写JavaScript代码时，遵循良好的变量命名规范对于提高代码的可读性、可维护性和协作效率至关重要。一个清晰且一致的命名习惯不仅有助于开发者自己理解代码，也能让其他团队成员更容易上手和维护项目。本文将详细介绍JavaScript中常见的变量命名规则和…...
2025年渗透测试面试题总结-拷打题库05（题目+回答）
网络安全领域各种资源，学习文档，以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具，欢迎关注。 目录 2025年渗透测试面试题总结-拷打题库05 1. 病毒和蠕虫的区别 2. DNS欺骗（DNS Spoofing&…...
【排队论】Probabilistic Forecasts of Bike-Sharing Systems for Journey Planning
Probabilistic Forecasts of Bike-Sharing Systems forJourney Planning abstract 我们研究了对共享单车系统（BSS）车站未来自行车可用性进行预测的问题。这是相关的，以便提出建议，保证用户能够进行旅行的概率足够高。为此&#x…...
Redis 的持久化机制（RDB, AOF）对微服务的数据一致性和恢复性有何影响？如何选择？
Redis 的持久化机制（RDB 和 AOF）对于保证 Redis 服务重启或崩溃后数据的恢复至关重要，这直接影响到依赖 Redis 的微服务的数据一致性和恢复能力。 1. RDB (Redis Database Backup) 机制: 在指定的时间间隔内，将 Redis 在内存中的…...
手撕LLM（四）：从源码出发，探索大模型的预训练（pretrain）过程
前面我们基于Minimind项目介绍了大模型的推理、LoRa加载、Moe结构， 大家对大模型的整体结构应该有一个比较清晰的认识；从该篇博客开始，我们通过代码剖析大模型的训练过程，今天的主题是大模型的预训练。 那大模型的预训练是一个什么…...
Linux系统：进程终止的概念与相关接口函数（_exit,exit,atexit）
本节目标 理解进程终止的概念理解退出状态码的概念以及使用方法掌握_exit与exit函数的用法以及区别atexit函数注册终止时执行的函数相关宏 一、进程终止 进程终止（Process Termination）是指操作系统结束一个进程的执行，回收其占用的资源&a…...
keil5 µVision 升级为V5.40.0.0：增加了对STM32CubeMX作为全局生成器的支持，主要有哪些好处？
在Keil5 μVision V5.40.0.0版本中，增加了对STM32CubeMX作为全局生成器的支持，这一更新主要带来了以下三方面的提升： 开发流程整合STM32CubeMX原本就支持生成Keil项目代码，但新版本将这一集成升级为“全局生成器”级别，意味着STM32CubeMX生成的代码能直接成为Keil项目的核…...
C 语言联合与枚举：自定义类型的核心解析
上篇博客中，我们通过学习了解了C语言中一种自定义类型结构体的相关知识，那么该语言中是否还拥有相似的自定义类型呢？这将是我们今天学习的目标。 1.联合体 联合体其实跟结构体类似，也是由一个或多个成员构成，这些成员…...
P1113 杂务-拓扑排序
拓扑排序 P1113 杂务 题目来源-洛谷 题意 求出完成所有任务的最短时间 思路 要求完成所有任务的最短时间，即每个任务尽可能最短，所以再求完成所有任务中的最大值（需要最长时间的任务都完成了才叫全部完成） 问题化解…...
Flink介绍——实时计算核心论文之Kafka论文总结
引入 大数据系统中的数据来源 在开始深入探讨Kafka之前，我们得先搞清楚一个问题：大数据系统中的数据究竟是从哪里来的呢？其实，这些数据大部分都是由各种应用系统或者业务系统产生的“日志”。 比如，互联网公司的广告…...
模拟投资大师思维：AI对冲基金开源项目详解
这里写目录标题 引言项目概述核心功能详解多样化的AI投资智能体灵活的运行模式透明的决策过程 安装和使用教程环境要求安装步骤基本使用方法运行对冲基金模式运行回测模式 应用场景和实际价值教育和研究价值潜在的商业应用与现有解决方案的对比局限性与发展方向 结论 引言 随着…...
DAY4:数据库对象与高级查询深度解析：从视图到多表关联实战
一、数据库对象精要指南 1.1 视图（View）的进阶应用 视图是存储在数据库中的虚拟表，本质是预编译的SQL查询语句。通过视图可以简化复杂查询、实现数据安全隔离、保持业务逻辑一致性。 创建语法示例： CREATE VIEW sales_summary…...
【Matlab】中国东海阴影立体感地图
【Matlab】中国东海阴影立体感地图 【Matlab】中国东海阴影立体感地图 【Matlab】中国东海阴影图立体感画法 以前分享过一次，链接如下： 中国海域地形图 但是以前还是有些小问题，这次修改了。 另外，增加了新的画法： 另…...
python文件类操作：json/ini配置文件、logging日志统计、excel表格数据读写、os操作库
文章目录 一、with open文件操作二、csv表格数据读写三、Excel表格数据读写四、json配置文件读写五、ini配置文件读写六、logging日志统计七、os操作库（文件拼接、创建、判断等） 打开文件使用不同参数有着不同的含义，比如只读、只写、二进制读…...
VSCode安装与环境配置（Mac环境）
20250419 - 概述 大概是非常久之前了，装了VSCode，估计都得21的时候了，电脑上也没更新过。当时安装也直接装上就完事了。这次把版本更新一下，同时记录一下这个安装过程。 安装 mac下安装非常简单，直接从官网下载&am…...
【信息系统项目管理师】高分论文：论信息系统项目的采购管理（“营业工单系统”项目）
更多内容请见： 备考信息系统项目管理师-专栏介绍和目录 文章目录 论文1、规划采购管理2、实施采购3、控制采购论文 2018年1月，我参加了 XX运营商集团公司某省分公司的“营业工单系统”的信息化建设项目，我有幸担任项目经理。该项目投资1000万元人民币，建设工期为12个月。该…...
XCVU13P-2FHGA2104I Xilinx Virtex UltraScale+ FPGA
XCVU13P-2FHGA2104I 是 Xilinx（现为 AMD）Virtex UltraScale™ FPGA 系列中的高端 Premium 器件，基于 16nm FinFET 工艺并采用 3D IC 堆叠硅互连（SSI）技术，提供业内顶级的计算密度和带宽。该芯片集成约 3,…...
@Validated与@Valid的正确使用姿势
验证代码 Validated RestController public class A {PostMappingpublic void test(Min(value 1) Integer count) {} // 校验规则生效 }RestController public class A {PostMappingpublic void test(Validated Min(value 1) Integer count) {} // 校验规则不生效 }RestCont…...
Ubuntu20.04下Docker方案实现多平台SDK编译
0 前言 熟悉嵌入式平台Linux SDK编译流程的小伙伴都知道，假如平台a要求必须在Ubuntu18.04下编译，平台b要求要Ubuntu22.04的环境，那我只有Ubuntu20.04，或者说我的电脑硬件配置最高只能支持Ubuntu20.04怎么办？强行在Ubuntu20.04下编译，编又编不过，换到旧版本我又不愿意，…...
树莓派配置GPIO)
树莓派超全系列教程文档--(34)树莓派配置GPIO
配置GPIO GPIO控制gpio 文章来源： http://raspberry.dns8844.cn/documentation 原文网址 GPIO控制 gpio 通过 gpio 指令，可以在启动时将 GPIO 引脚设置为特定模式和值，而以前需要自定义 dt-blob.bin 文件。每一行都对一组引脚应用相同的设…...
)
C语言 数组(下)
目录 1.二维数组的创建 2.二位数组的初始化 3.二维数组的使用 4.二维数组在内存中的储存 1.二维数组的创建 1.1二维数组的概念 前面学习的数组被称为一维数组，数组的元素都是内置类型的，如果我们把一维数组做为数组的元 素，这时候就是…...
opencv图像旋转(单点旋转的原理）
首先我们以最简单的一个点的旋转为例子，且以最简单的情况举例，令旋转中心为坐标系中心O（0，0），假设有一点P_{0}(x_{0},y_{0})，P_{0}离旋转中心O的距离为r，OP_{0}与坐标轴x轴的夹角为\…...
针对MCP认证考试中的常见技术难题进行实战分析与解决方案分享
一、身份与权限管理类难题 场景1：Active Directory组策略（GPO）不生效 问题现象：客户端计算机未应用新建的组策略。排查步骤： 检查GPO链接顺序：使用gpresult /r查看策略优先级，确保目标OU的GPO…...
systemctl管理指令
今天我们来继续学习服务管理指令,接下来才是重头戏-systemctl,那么话不多说,直接开始吧. systemctl管理指令 1.基本语法: systemctl [start | stop | restart | status]服务 注：systemctl指令管理的服务在/usr/lib/ systemd/system查看 2.systemctl设置服务的自…...
DataWhale AI春训营 问题汇总
1.没用下载训练集导致出错，爆错如下。 这个时候需要去比赛官网下载对应的初赛训练集 unzip -d /mnt/workspace/sais_third_new_energy_baseline/data /mnt/workspace/sais_third_new_energy_baseline/初赛训练集.zip 在命令行执行这个命令解压 2.没定义测试集 te…...
当算力遇上马拉松：一场科技与肉身的极限碰撞
目录 一、从"肉身苦修"到"科技修仙" 二、马拉松的"新大陆战争" 三、肉身会被算法"优化"吗？ 马拉松的下一站是"人机共生"时代 当AI能预测你的马拉松成绩，算法能规划最佳补给方案，智能装备让训练效率翻倍——你还会用传…...
n8n 中文系列教程_02. 自动化平台深度解析：核心优势与场景适配指南
在低代码与AI技术深度融合的今天，n8n作为开源自动化平台正成为开发者提效的新利器。本文深度剖析其四大核心技术优势——极简部署、服务集成、AI工作流与混合开发模式，并基于真实场景测试数据，厘清其在C端高并发、多媒体处理等场景的边界。 一…...
Macvlan 网络类型详解：特点、优势与局限性
一、Macvlan 网络类型的基本概念 1. 什么是 Macvlan Macvlan 是 Linux 内核提供的一种网络虚拟化技术，允许在单个物理接口（例如 enp0s3）上创建多个虚拟网络接口。每个虚拟接口拥有独立的 MAC 地址，表现得像物理网络中的独立设备…...
tigase源码学习杂记-AbstractMessageReceiver
前言 废话，最近把工作中用的基于XMPP协议的经典开源框架又读了一遍，整理一下其优秀的源码学习记录。 概述 AbstractMessageReceiver是tigase核心组件MessageRouter、SessionManager的抽象父类，是tigase消息接收器的抽象。AbstractMessageR…...
C#.net core部署IIS
Windows IIS 部署 .NET 应用详细指南 本文档提供了在 Windows Server 上使用 IIS 部署 .NET 应用（包括 .NET Core 和传统 WebForms）的完整步骤和最佳实践。 目录 概述环境准备.NET Core 应用部署 应用准备发布应用在 IIS 中配置应用池配置高级配置 .N…...
sql学习
Name 列中选取唯一不同的值 插入 更新 删除 筛选固定的行数 模糊查询 包含 范围 name的别名是n 两个表交集 左边包含全部 右边包含全部 重复的展示一条 重复的都会展示 创建一个新表，把字段复制近期 创建数据库 约束 创建索引 删除 函数 聚合函数...
OSPF实验
实验要求： 1.R5为ISP，其上只能配置IP地址；R4作为企业边界路由器， 出口公网地址需要通过PPP协议获取，并进行chap认证 （上面这个不会做） 2.整个OSPF环境IP基于172.16.0.0/16划分； 3.所…...
洛谷题目：P8624 [蓝桥杯 2015 省 AB] 垒骰子 题解 （本题简）
题目传送门： P8624 [蓝桥杯 2015 省 AB] 垒骰子 - 洛谷 (luogu.com.cn) 前言： 这道题要求我们计算将 个骰子垒成柱体且满足某些面不能紧贴的不同垒骰字方式的数量，并且结果需要对 取模。下面小亦来带大家逐步分析解题思路： #基本概念理解： 1、骰子特性： 一直骰子的…...
简单线段树的讲解（一点点的心得体会）
目录 一、初识线段树 图例： 编辑 数组存储： 指针存储： 理由： build函数建树 二、线段树的区间修改维护 区间修改维护： 区间修改的操作： 递归更新过程： 区间修改update：…...
在 Node.js 中使用原生 `http` 模块，获取请求的各个部分：**请求行、请求头、请求体、请求路径、查询字符串** 等内容
在 Node.js 中使用原生 http 模块，可以通过 req 对象来获取请求的各个部分：请求行、请求头、请求体、请求路径、查询字符串 等内容。 ✅ 一、基础结构 const http require(http); const url require(url);const server http.createServer((req, res)…...
深度学习--mnist数据集实现卷积神经网络的手写数字识别
文章目录 一、卷积神经网络CNN1、什么是CNN2、核心3、构造 二、案例1、下载数据集（训练、测试集）并展示画布2、打包数据图片3、判断系统使用的是CPU还是GPU4、定义CNN神经网络5、训练和测试模型 一、卷积神经网络CNN 1、什么是CNN 卷积神经网络是一种深…...
python基础知识点（1）
python语句 一行写一条语句 一行内写多行语句，使用分号分隔建议每行写一句，且结束时不写分号写在[ ]、{ }内的跨行语句，被视为一行语句\ 是续行符,实现分行书写功能 反斜杠表示下一行和本行是同一行 代码块与缩进 代码块复合语句…...
详解反射型 XSS 的后续利用方式：从基础窃取到高级组合拳攻击链
在网络安全领域，反射型跨站脚本攻击（Reflected Cross-Site Scripting，简称反射型 XSS）因其短暂的生命周期和临时性，常被视为“低危”漏洞，威胁性不如存储型或 DOM 型 XSS。然而，这种看法低估了它…...
【问题笔记】解决python虚拟环境运行脚本无法激活问题
【问题笔记】解决python虚拟环境运行脚本无法激活问题 错误提示问题所在解决方法**方法 1：临时更改执行策略****方法 2：永久更改执行策略** **完整流程示例** 错误提示 PS F:\PythonProject\0419graphrag-local-ollama-main> venv1\Scripts\activate…...
CF148D Bag of mice
题目传送门 思路 状态设计 设 d p i , j dp_{i, j} dpi,j 表示袋中有 i i i 个白鼠和 j j j 个黑鼠时， A A A 能赢的概率。 状态转移 现在考虑抓鼠情况： A A A 抓到白鼠：直接判 A A A 赢，概率是 i i j \frac{i}{i j}…...
精益数据分析（6/126）：深入理解精益分析的核心要点
精益数据分析（6/126）：深入理解精益分析的核心要点 在创业和数据驱动的时代浪潮中，我们都在不断探索如何更好地利用数据推动业务发展。我希望通过和大家分享对《精益数据分析》的学习心得，一起在这个充满挑战和机遇的领…...
package.json ^、~、＞、＞=、* 详解
package.json ^、~、>、>、* 详解 在 Vue 项目中，package.json 文件的依赖项（dependencies）和开发依赖项（devDependencies）中，版本号前可能会带有一些特殊符号，例如 ^、~、>、<、&g…...
2025年赣教云智慧作业微课PPT模板
江西的老师们注意，2025年赣教云智慧作业微课PPT模版和往年不一样，千万不要搞错了，图上的才是正确的2025年的赣教云智慧作业微课PPT模版，赣教云智慧作业官网有问题，无法正确下载该模板，需要该模板的…...