当前位置: 首页 > 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…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...