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

信息学奥赛一本通 1416:【17NOIP普及组】棋盘 | 洛谷 P3956 [NOIP2017 普及组] 棋盘

【题目链接】

洛谷 P3956 [NOIP2017 普及组] 棋盘
ybt 1416:【17NOIP普及组】棋盘

【题目考点】

1. 深搜:深搜回溯
2. 深搜剪枝:最优化剪枝

【解题思路】

搜索从左上角到右下角的所有走法中花费金币最少的走法。
需要使用深搜回溯,搜索从一点出发到另一点的所有路径。
设二维数组mp记录每个格子的颜色,如果无色记为-1,1是黄色,0是红色。
在某次搜索时,当前位置为(sx, sy),下一个要访问的位置为(x, y),已经使用金币coin。
如果当前位置(sx,sy)是有色的

  • 如果下一个位置(x,y)是有色的
    • 如果二者颜色相同,到下个位置时花的金币数coin不变
    • 如果颜色不同,到下个位置花的金币数coin加1。
  • 如果下一个位置(x,y)是无色的
    • 将下一个位置通过魔法变为与(sx, sy)同色,到下个位置的金币数coin加2,

如果当前位置(sx, sy)是无色的,但是变成了col色。那么下个位置(x, y)不可以是无色的。
如果下个位置(x,y)是有色的,那么

  • 如果(x,y)位置的颜色和col相同,那么到下个位置时花的金币数coin不变
  • 如果(x,y)位置的颜色和col不同,到下个位置花的金币数coin加1。

设二维数组mc,mc[i][j]表示到达(i, j)位置时花的最少金币数。
最优性剪枝:如果到(sx, sy)位置花的钱数coin比已知的一种到(sx, sy)位置的走法花钱mc[sx][sy]相等或更多,则没必要再搜索了,直接返回。
这里必须进行最优性剪枝,否则搜索会超时。

【题解代码】

解法1:深搜
#include<bits/stdc++.h>
using namespace std;
#define N 105
#define INF 0x3f3f3f3f
int m, n, mp[N][N], minCoin = INF, mc[N][N];//mp[i][j]:为1代表黄色,0代表红色,-1代表无色 mc[i][j],到i,j的最小钱数 
int dir[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};
bool vis[N][N];
void dfs(int sx, int sy, int coin, int col)//col:如果(sx,sy)本来是无色,col为(sx,sy)通过魔法变化后的颜色 
{if(coin >= mc[sx][sy])//最优化剪枝,如果到当前位置花的钱数比已知的一种到当前位置的走法花钱更多,则没必要再搜索了。 return;elsemc[sx][sy] = coin;if(sx == m && sy == m)//到达终点点 return; for(int i = 0; i < 4; ++i){int x = sx + dir[i][0], y = sy + dir[i][1];//x,y是sx,sy周围的位置 if(x >= 1 && x <= m && y >= 1 && y <= m && !vis[x][y]){vis[x][y] = true;if(mp[sx][sy] == 1 || mp[sx][sy] == 0)//如(sx, sy)是红黄 {if(mp[x][y] == -1)//如果下一个位置无色 dfs(x, y, coin + 2, mp[sx][sy]);//变成与出发点相同的颜色 else if(mp[x][y] == mp[sx][sy])//颜色相同 dfs(x, y, coin, -1);else//颜色不同 dfs(x, y, coin + 1, -1);}else if(mp[sx][sy] == -1 && mp[x][y] != -1)//如(sx, sy)是无色 {//如果无色的下一个格子还是无色,则不访问 if(mp[x][y] == col)//颜色相同 dfs(x, y, coin, -1);						else//颜色不同 dfs(x, y, coin + 1, -1);}vis[x][y] = false;}}
}
int main()
{int x, y, c;memset(mp, -1, sizeof(mp));cin >> m >> n;for(int i = 1; i <= n; ++i){cin >> x >> y >> c;mp[x][y] = c;}memset(mc, 0x3f, sizeof(mc));dfs(1, 1, 0, -1);if(mc[m][m] == INF)cout << -1;elsecout << mc[m][m];return 0;
}

相关文章:

信息学奥赛一本通 1416:【17NOIP普及组】棋盘 | 洛谷 P3956 [NOIP2017 普及组] 棋盘

【题目链接】 洛谷 P3956 [NOIP2017 普及组] 棋盘 ybt 1416&#xff1a;【17NOIP普及组】棋盘 【题目考点】 1. 深搜&#xff1a;深搜回溯 2. 深搜剪枝&#xff1a;最优化剪枝 【解题思路】 搜索从左上角到右下角的所有走法中花费金币最少的走法。 需要使用深搜回溯&…...

UE4完整教程 UE4简介 UE4学习攻略及文件格式

开头附上工作招聘面试必备问题噢~~包括综合面试题、无领导小组面试题资源文件免费!全文干货。 UE4简介学习攻略UE4Demo代码面试内容资源-CSDN文库https://download.csdn.net/download/m0_72216164/89825102 工作招聘无领导小组面试全攻略最常见面试题(第一部分)共有17章+可…...

JVM内存回收机制

目录 1.JVM运行时数据区 2.JVM类加载过程 3.双清委派模型 4.垃圾回收机制&#xff08;GC&#xff09; 找出谁是垃圾方案一&#xff1a;引用计数 找出谁是垃圾&#xff1a;方案二&#xff0c;可达性分析 释放垃圾的内存空间 判断垃圾&#xff1a;jvm依据对象的年龄对 对象…...

中国身份证号码校验

题目描述 第二届河南省最美教师评选开始了&#xff0c;每一位同学都可以投票选出你支持的人选&#xff0c;但是为了防止刷票&#xff0c;必须通过身份验证才可投票。负责投票平台后台的老大爷希望你能帮他验证身份证号的合法性&#xff0c;防止那些熊孩子随意刷票&#xff0c;…...

【Kubernetes】常见面试题汇总(五十四)

目录 120.创建 init C 容器后&#xff0c;其状态不正常&#xff1f; 特别说明&#xff1a; 题目 1-68 属于【Kubernetes】的常规概念题&#xff0c;即 “ 汇总&#xff08;一&#xff09;~&#xff08;二十二&#xff09;” 。 题目 69-113 属于【Kubernetes】的生产…...

不懂外语也能无障碍交流?探索4款超好用中英翻译工具

嘿&#xff0c;各位外贸流程的小伙伴们&#xff0c;今儿咱们来聊聊那些翻译神器&#xff0c;看看它们在中英文互译这条路上&#xff0c;是怎么给我们这些天天跟洋文打交道的哥们儿姐们儿减轻负担的。我亲身体验了福昕翻译在线、福昕翻译大师、海鲸AI翻译还有腾讯翻译君&#xf…...

C++ WebDriver扩展

概述 WebDriver协议基于HTTP&#xff0c;使用JSON进行数据传输&#xff0c;定义了client与driver之间的通信标准。无论client的实现语言&#xff08;如Java或C#&#xff09;&#xff0c;都能通过协议中的endpoints准确指示driver执行各种操作&#xff0c;覆盖了Selenium的所有功…...

WeChat_DevTools 断点调试方法总结

新建工程&#xff0c;以小程序 login 调试为例&#xff0c;代码如下&#xff1a; // 登录wx.login({success: res > {// 发送 res.code 到后台换取 openId, sessionKey, unionIddebugger;resThis this;wx.showModal({title: 登录成功,content: res.code res.code,comple…...

水波荡漾效果+渲染顺序+简单UI绘制

创建场景及布置 创建新场景Main,在Main场景中创建一个plane物体&#xff0c;命名为WaterWavePla,具体数值及层级面板排布如下&#xff1a; 编写脚本 创建一个文件夹&#xff0c;用于存放脚本&#xff0c;命名Scripts,创建一个子文件夹Effect,存放特效相关脚本&#xff0c;创建…...

深度学习中的结构化概率模型 - 使用图来描述模型结构篇

序言 在深度学习的探索之路上&#xff0c;结构化概率模型以其独特的视角和强大的表达能力&#xff0c;成为了研究复杂数据关系的重要工具。这一模型的核心在于其巧妙地利用图来描述模型结构&#xff0c;将随机变量间的复杂交互关系可视化、结构化。图的引入&#xff0c;不仅为…...

C语言中的栈帧

------------------------ | 局部变量区 | | (根据变量声明而变化) | ------------------------ | 参数区 | | (根据函数原型而变化) | ------------------------ | (可选) 保存寄存器区 | | (编译器/架构特定) | -…...

vue数组根据某些条件进行二次切割

原本的一个一维数组首先 1.根据depnm和bed的不同会分成不同的数组 2.在条件1的基础上分割出来的数组如果存在里面有isBgn1的会进行二次分割 比如原数组是[{depnm:1,bed:2,isBgn:0},{}……] 根据条件一会组成一个二维数组得到 [ [①depnm值一致的一个一维数组], [②bed值一…...

Yolov8改进轻量级网络Ghostnetv2

1,理论部分 轻量级卷积神经网络 (CNN) 专为移动设备上的应用程序而设计,具有更快的推理速度。卷积运算只能捕获窗口区域中的局部信息,这会阻止性能进一步提高。将自我注意引入卷积可以很好地捕获全局信息,但会在很大程度上阻碍实际速度。在本文中,我们提出了一种硬件友好…...

【Spring】@RequestMapping、@RestController和Postman

文章目录 1.RequestMapping 注解介绍2. RequestMapping 使用3. RequestMapping 是 GET 还是 POST 请求&#xff1f;GET 请求POST 请求指定 GET/POST 方法类型 2. Postman 介绍1. 创建请求2. 传参介绍1. 普通传参2. form-data3. x-www-form-urlencoded form 表单&#xff0c;对应…...

【深度学习基础模型】回声状态网络(Echo State Networks, ESN)详细理解并附实现代码。

【深度学习基础模型】回声状态网络&#xff08;Echo State Networks, ESN&#xff09;详细理解并附实现代码。 【深度学习基础模型】回声状态网络&#xff08;Echo State Networks, ESN&#xff09;详细理解并附实现代码。 文章目录 【深度学习基础模型】回声状态网络&#xf…...

Redis的基础认识与在ubuntu上的安装教程

来自Redis的自我介绍 我是Redis&#xff0c;一个中间件&#xff0c;职责是把数据存储在内存上&#xff0c;因此可以作为数据库、缓存、消息队列等场景使用。由于可以把数据存储在内存上&#xff0c;因此江湖人称快枪手 1.redis的功能特性 &#xff08;1&#xff09;数据在内存…...

鸿蒙harmonyos next flutter混合开发之ohos工程引用 har 文件

创建鸿蒙原生工程MyApplication。创建flutter module&#xff0c;生成har文件&#xff0c;并且将flutter module中.ohos文件entryability/EntryAbility.ets、pages/Index.ets分别替换MyApplication中的。 # 1. 创建 flutter子模块工程 flutter create -t module my_flutter_…...

react-问卷星项目(5)

实战 路由 路由设计&#xff0c;网址和页面的关系&#xff0c;就是从业务上分析需要哪些页面哪些页面内容可以抽离&#xff0c;业务流程要有入有出增加页面和Layout模版&#xff0c;模版就是抽离页面公共部分&#xff0c;比如都有顶部或者左侧导航&#xff0c;直接上代码&…...

08.useInterval

在 React 应用中,实现定时器功能通常需要使用 setInterval() 和 clearInterval(),这可能会导致代码复杂和难以维护。useInterval 钩子提供了一种声明式的方法来实现定时器功能,使得定时器的管理更加简单和直观。这个自定义钩子不仅简化了定时器的使用,还解决了一些常见的定…...

【Android 源码分析】Activity生命周期之onDestroy

忽然有一天&#xff0c;我想要做一件事&#xff1a;去代码中去验证那些曾经被“灌输”的理论。                                                                                  – 服装…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...