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

棋盘(c++题解)

题目描述

有一个m × m的棋盘,棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。 任何一个时刻,你所站在的位置必须是有颜色的(不能是无色的) ,你只能向上、下、 左、右四个方向前进。当你从一个格子走向另一个格子时,如果两个格子的颜色相同,那你不需要花费金币;如果不同,则你需要花费 1 个金币。 另外,你可以花费 2 个金币施展魔法让下一个无色格子暂时变为你指定的颜色。但这个魔法不能连续使用,而且这个魔法的持续时间很短,也就是说,如果你使用了这个魔法,走到了这个暂时有颜色的格子上,你就不能继续使用魔法;只有当你离开这个位置,走到一个本来就有颜色的格子上的时候,你才能继续使用这个魔法,而当你离开了这个位置(施展魔 法使得变为有颜色的格子)时,这个格子恢复为无色。 现在你要从棋盘的最左上角,走到棋盘的最右下角,求花费的最少金币是多少?

【输入】

数据的第一行包含两个正整数 m,n,以一个空格分开,分别代表棋盘的大小,棋盘上有颜色的格子的数量。  接下来的 n 行,每行三个正整数 x,y,c,分别表示坐标为(x,y)的格子有颜色 c。 其中 c=1 代表黄色,c=0 代表红色。相邻两个数之间用一个空格隔开。棋盘左上角的坐标 为(1, 1),右下角的坐标为(m, m)。  棋盘上其余的格子都是无色。保证棋盘的左上角,也就是(1,1)一定是有颜色的。

【输出】

输出一行,一个整数,表示花费的金币的最小值,如果无法到达,输出-1。

【输入样例】

复制5 7
1 1 0
1 2 0
2 2 1
3 3 1
3 4 0
4 4 1
5 5 0

【输出样例】

复制8

【提示】

【输入输出样例 1 说明】

从(1,1)开始,走到(1,2)不花费金币

从(1,2)向下走到(2,2)花费 1 枚金币

从(2,2)施展魔法,将(2,3)变为黄色,花费 2 枚金币

从(2,2)走到(2,3)不花费金币

从(2,3)走到(3,3)不花费金币

从(3,3)走到(3,4)花费 1 枚金币

从(3,4)走到(4,4)花费 1 枚金币 从(4,4)施展魔法,将(4,5)变为黄色,花费 2 枚金币,

从(4,4)走到(4,5)不花费金币

从(4,5)走到(5,5)花费 1 枚金币

共花费 8 枚金币。

【输入输出样例 2】

输入:

复制5 5
1 1 0
1 2 0
2 2 1
3 3 1
5 5 0

输出:

复制-1

【输入输出样例 2 说明

从(1,1)走到(1,2),不花费金币

从(1,2)走到(2,2),花费 1 金币

施展魔法将(2,3)变为黄色,并从(2,2)走到(2,3)花费 2 金币

从(2,3)走到(3,3)不花费金币

从(3,3)只能施展魔法到达(3,2),( 2,3),( 3,4),(4,3) 而从以上四点均无法到达(5,5),故无法到达终点,输出-1

【数据规模与约定】

对于 30%的数据,1 ≤ m ≤ 5, 1 ≤ n ≤ 10。

对于 60%的数据,1 ≤ m ≤ 20, 1 ≤ n ≤ 200。

对于 100%的数据,1 ≤ m ≤ 100, 1 ≤ n ≤ 1,000。

_____________________________________________________________________________

写作不易,点个赞呗!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 

_____________________________________________________________________________

#include <bits/stdc++.h>
using namespace std;
int n,m,ans=INT_MAX;
int a[105][105];
bool b[105][105];
int d[105][105];
int f[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
void dfs(bool flag,int h,int x,int y,int c){if(d[x][y]<=h)return;if(h>=ans)return;d[x][y]=h;if(x==n&&y==n)ans=h;for(int i=0;i<4;i++){int dx=x+f[i][0],dy=y+f[i][1];if(dx<1||dy<1||dx>n||dy>n||b[dx][dy])continue;if(flag&&a[dx][dy]==0)continue;b[dx][dy]=true;if(a[dx][dy]==0)dfs(true,h+2,dx,dy,c);else if(a[dx][dy]==c)dfs(false,h,dx,dy,c);else if(a[dx][dy]!=c)dfs(false,h+1,dx,dy,a[dx][dy]);b[dx][dy]=false;}
}
int main() {memset(d,63,sizeof(d));cin>>n>>m;for(int i=1;i<=m;i++){int X,Y,c;cin>>X>>Y>>c;a[X][Y]=c+1;}dfs(false,0,1,1,a[1][1]);if(ans==INT_MAX)cout<<"-1";else cout<<ans;
}

相关文章:

棋盘(c++题解)

题目描述 有一个m m的棋盘&#xff0c;棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。 任何一个时刻&#xff0c;你所站在的位置必须是有颜色的&#xff08;不能是无色的&#xff09; &#xff0c;你只能向上、下、 左、右…...

滑动窗口例题

一、209:长度最小的子数组 209:长度最小的子数组 思路&#xff1a;1、暴力解法&#xff1a;两层for循环遍历&#xff0c;当sum > target时计算子数组长度并与result比较&#xff0c;取最小的更新result。提交但是超出了时间限制。 class Solution {public int minSubArray…...

智过网:注册安全工程师注册有效期与周期解析

在职业领域&#xff0c;各种专业资格认证不仅是对从业者专业能力的认可&#xff0c;也是保障行业安全、规范发展的重要手段。其中&#xff0c;注册安全工程师证书在安全生产领域具有举足轻重的地位。那么&#xff0c;注册安全工程师的注册有效期是多久呢&#xff1f;又是几年一…...

腐蚀Rust 服务端搭建架设个人社区服务器Windows教程

腐蚀Rust 服务端搭建架设个人社区服务器Windows教程 大家好我是艾西&#xff0c;一个做服务器租用的网络架构师也是游戏热爱者。最近在steam发现rust腐蚀自建的服务器以及玩家还是非常多的&#xff0c;那么作为服务器供应商对这商机肯定是不会放过的哈哈哈&#xff01; 艾西这…...

蓝桥杯备赛:考前注意事项

考前注意事项 1、DevCpp添加c11支持 点击 工具 - 编译选项 中添加&#xff1a; -stdc112、万能头文件 #include <bits/stdc.h>万能头文件的缺陷&#xff1a;y1 变量 在<cmath>中用过了y1变量。 #include <bits/stdc.h> using namespace std;// 错误示例 …...

111111111111

111111111111...

uniapp 卡片勾选

前言 公司的app项目使用的uniapp&#xff0c;项目里有一个可勾选的卡片功能&#xff0c;效果图如下&#xff1a; 找了一圈没找到什么太好的组件&#xff0c;于是就自己简单写了一个&#xff0c;记录一下。避免以后还会用到 代码 <template><view class"card-…...

乐趣Python——文件与数据:挥别乱糟糟的桌面

各位朋友们&#xff0c;今天我们要开启一场非凡的冒险——进入文件操作的世界&#xff01;你知道吗&#xff0c;在你的电脑里&#xff0c;有一个叫做“文件系统”的迷宫&#xff0c;里面藏着各种各样的文件和文件夹&#xff0c;它们就像是迷宫中的宝藏。但有时候&#xff0c;这…...

docker nginx-lua发送post json 请求

环境准备 dockerfile from fabiocicerchia/nginx-lua:1.25.3-ubuntu22.04 run apt-get -qq update && apt-get -qq install luarocks run luarocks install lua-cjson run luarocks install lua-iconv run luarocks install lua-resty-http后台代理服务准备&#xff…...

阿里面试总结 一

写了这些还是不够完整&#xff0c;阿里 字节 卷进去加班&#xff01;奥利给 ThreadLocal 线程变量存放在当前线程变量中&#xff0c;线程上下文中&#xff0c;set将变量添加到threadLocals变量中 Thread类中定义了两个ThreadLocalMap类型变量threadLocals、inheritableThrea…...

多线程(49)定义无锁、阻塞、非阻塞和无等待算法

在并发编程中&#xff0c;理解不同的同步策略——无锁&#xff08;Lock-Free&#xff09;、阻塞&#xff08;Blocking&#xff09;、非阻塞&#xff08;Non-Blocking&#xff09;、无等待&#xff08;Wait-Free&#xff09;——对于设计高效、健壮的多线程应用至关重要。让我们…...

(一)ffmpeg 入门基础知识

一、ffmpeg FFmpeg是一套强大的开源音视频处理工具&#xff0c;能够录制、转换以及流化音视频内容。 FFmpeg是开源的&#xff0c;这意味着它的源代码是公开的&#xff0c;允许任何人使用、修改和分发。它提供了录制、转换以及流化音视频的完整解决方案&#xff0c;支持多种格…...

【软件测试】个人博客系统测试

个人博客系统测试 一、项目背景1.1 技术背景1.2 功能背景 二、 测试用例编写三、自动化测试3.1 什么是自动化测试3.2 通过使用selenium进行自动化测试的编写&#xff08;Java实现&#xff09;3.3 编写测试用例&#xff0c;执行自动化测试3.3.1 输入用户名:test,密码:123&#x…...

20240410解决OK3588-C的核心板刷机之后无法启动的问题

20240410解决OK3588-C的核心板刷机之后无法启动的问题 2024/4/10 19:38 1、编译OK3588的LINUX/Buildroot&#xff1f;forlinxubuntu: ~/3588/OK3588_Linux_fs$ sudo ./build.sh BoardConfig-linuxfs-ok3588.mk 2、进行全编译 forlinxubuntu: ~/3588/OK3588_Linux_fs$ sudo ./bu…...

仅需三步就能成为大语言模型Prompt Engineer提示词工程大神

AI Prompt Engineer(提示词工程)是当下GenAI行业最热门的话题&#xff0c;它是利用有效的AI模型交互提示技术&#xff0c;引导大语言模型生成更高质量、更准确、更相关的回应。相对于预训练和微调&#xff0c;提示词工程不需要标注数据和训练模型&#xff0c;极大的节约了时间和…...

RuleEngine规则引擎底层改造AviatorScript 之公式规则

前情提要&#xff0c;看上一个文章&#xff0c;具体要实现的效果就是 当然上来的问题就是前端的问题&#xff0c;这个框首先他们用的是富文本&#xff0c;富文本传到后台的结果是前端脚本&#xff0c;带着h5的标签&#xff0c;后面改成了这个&#xff0c;当时这个东西其实和后…...

Vue项目(H5)与微信小程序来回跳转

新建H5页面 在小程序里面新建一个名为H5的文件夹&#xff0c;以及H5页面 H5.WXML <web-view src"{{h5Url}}" bindmessage"handleGetMessage"></web-view>H5.JSdata: { h5Url:https://xxx.com/login 要跳转的H5页面},H5回来的回调方法handleG…...

设计模式-单一职责原则

基本介绍 对类来说的&#xff0c;即一个类应该只负责一项职责。如类A负责两个不同的职责&#xff0c;职责1&#xff0c;职责2.当职责1需求变更而改变A时&#xff0c;可能造成职责2执行错误&#xff0c;所以需要将类A的粒度分解为A1&#xff0c;A2 应用实例 方案1 public cl…...

vue和nunjucks的变量插值的形式{{}}冲突

Nunjucks 中修改配置 const nunjucks require(nunjucks);const template_old nunjucks.renderString(template_old: Hello, {{name}}!, { name: World }); console.log(template_old); // 配置 Nunjucks 环境 nunjucks.configure({tags: {variableStart: $(, // 设置变量起始…...

多语言婚恋交友APP开发流程一览

近年来&#xff0c;随着全球化的发展和人们对跨文化交流的需求增加&#xff0c;多语言婚恋交友APP的需求逐渐增长。开发这类APP需要考虑到不同语言和文化下用户的需求&#xff0c;涉及到一系列独特的流程和挑战。本文将从专家角度为您解析多语言婚恋交友APP的开发流程&#xff…...

科研绘图升级:用CMplot为你的基因组文章制作高颜值SNP密度图(R实战)

科研绘图升级&#xff1a;用CMplot为你的基因组文章制作高颜值SNP密度图&#xff08;R实战&#xff09; 在基因组学研究中&#xff0c;数据可视化不仅是结果展示的手段&#xff0c;更是科学叙事的重要语言。一张精心设计的SNP密度图&#xff0c;能够直观呈现全基因组范围内单核…...

从网线到数据包:手把手拆解以太网帧,搞懂GMAC接口到底在忙啥

从网线到数据包&#xff1a;手把手拆解以太网帧&#xff0c;搞懂GMAC接口到底在忙啥 当我们在浏览器输入一个网址&#xff0c;敲下回车键的瞬间&#xff0c;数据便开始了一场奇妙的旅程。这场旅程的起点&#xff0c;往往是一根不起眼的网线&#xff0c;而GMAC接口则是这场旅程中…...

NsEmuTools:5分钟搞定NS模拟器自动化管理的终极方案

NsEmuTools&#xff1a;5分钟搞定NS模拟器自动化管理的终极方案 【免费下载链接】ns-emu-tools 一个用于安装/更新 NS 模拟器的工具 项目地址: https://gitcode.com/gh_mirrors/ns/ns-emu-tools 你是否厌倦了手动安装和更新NS模拟器的繁琐过程&#xff1f;NsEmuTools作为…...

HFSS新手避坑指南:手把手教你设置Floquet Port和主从边界(附矩形波导实例)

HFSS阵列仿真实战&#xff1a;从Floquet Port到主从边界的精准设置 第一次打开HFSS准备仿真周期性结构时&#xff0c;那种既兴奋又忐忑的心情我至今记忆犹新。作为计算电磁学领域的黄金标准工具&#xff0c;HFSS在阵列天线、频率选择表面等周期性结构分析中展现出无可替代的价…...

5分钟上手Sticky:Linux桌面终极便签管理工具完全指南

5分钟上手Sticky&#xff1a;Linux桌面终极便签管理工具完全指南 【免费下载链接】sticky A sticky notes app for the linux desktop 项目地址: https://gitcode.com/gh_mirrors/stic/sticky 你是否厌倦了在电脑桌面上寻找重要信息的混乱体验&#xff1f;是否曾因为忘记…...

手把手教你用Intel System Debugger和DCI OOB盒子抓取开机日志(附CSME解码文件获取指南)

硬件调试实战&#xff1a;Intel System Debugger与DCI OOB盒子的替代方案指南 当主板开机卡死在LOGO界面或出现花屏时&#xff0c;传统调试工具链的突然失效往往让工程师陷入困境。我曾亲眼见过一位同事因为误改GDK7开发板的BIOS设置&#xff0c;导致价值上万的DCI-USB3调试线缆…...

EasyRules:轻量级规则引擎的实战入门

1. 为什么你需要了解EasyRules&#xff1f; 如果你是一名开发者&#xff0c;肯定遇到过这样的场景&#xff1a;业务逻辑越来越复杂&#xff0c;代码里充斥着大量的if-else嵌套&#xff0c;每次修改都要小心翼翼&#xff0c;生怕影响其他逻辑。我曾经维护过一个用户积分系统&…...

前后端分离林业产品推荐系统系统|SpringBoot+Vue+MyBatis+MySQL完整源码+部署教程

摘要 随着信息技术的快速发展&#xff0c;林业产品的销售和推广方式逐渐从传统线下模式转向数字化和智能化。林业产品种类繁多&#xff0c;消费者在选购时往往面临信息不对称的问题&#xff0c;难以高效匹配自身需求。同时&#xff0c;林业企业也缺乏精准的用户画像和推荐机制&…...

创业团队如何利用Taotoken进行多模型选型与成本控制

&#x1f680; 告别海外账号与网络限制&#xff01;稳定直连全球优质大模型&#xff0c;限时半价接入中。 &#x1f449; 点击领取海量免费额度 创业团队如何利用Taotoken进行模型选型与成本控制 对于初创团队的技术负责人而言&#xff0c;在有限的预算下既要满足快速迭代的产…...

E-Hentai下载器:免费漫画批量下载工具完整指南

E-Hentai下载器&#xff1a;免费漫画批量下载工具完整指南 【免费下载链接】E-Hentai-Downloader Download E-Hentai archive as zip file 项目地址: https://gitcode.com/gh_mirrors/eh/E-Hentai-Downloader 你是否曾经为了收藏喜欢的漫画而一页一页手动保存&#xff1…...