棋盘(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的棋盘,棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。 任何一个时刻,你所站在的位置必须是有颜色的(不能是无色的) ,你只能向上、下、 左、右…...
滑动窗口例题
一、209:长度最小的子数组 209:长度最小的子数组 思路:1、暴力解法:两层for循环遍历,当sum > target时计算子数组长度并与result比较,取最小的更新result。提交但是超出了时间限制。 class Solution {public int minSubArray…...
智过网:注册安全工程师注册有效期与周期解析
在职业领域,各种专业资格认证不仅是对从业者专业能力的认可,也是保障行业安全、规范发展的重要手段。其中,注册安全工程师证书在安全生产领域具有举足轻重的地位。那么,注册安全工程师的注册有效期是多久呢?又是几年一…...
腐蚀Rust 服务端搭建架设个人社区服务器Windows教程
腐蚀Rust 服务端搭建架设个人社区服务器Windows教程 大家好我是艾西,一个做服务器租用的网络架构师也是游戏热爱者。最近在steam发现rust腐蚀自建的服务器以及玩家还是非常多的,那么作为服务器供应商对这商机肯定是不会放过的哈哈哈! 艾西这…...
蓝桥杯备赛:考前注意事项
考前注意事项 1、DevCpp添加c11支持 点击 工具 - 编译选项 中添加: -stdc112、万能头文件 #include <bits/stdc.h>万能头文件的缺陷:y1 变量 在<cmath>中用过了y1变量。 #include <bits/stdc.h> using namespace std;// 错误示例 …...
111111111111
111111111111...
uniapp 卡片勾选
前言 公司的app项目使用的uniapp,项目里有一个可勾选的卡片功能,效果图如下: 找了一圈没找到什么太好的组件,于是就自己简单写了一个,记录一下。避免以后还会用到 代码 <template><view class"card-…...
乐趣Python——文件与数据:挥别乱糟糟的桌面
各位朋友们,今天我们要开启一场非凡的冒险——进入文件操作的世界!你知道吗,在你的电脑里,有一个叫做“文件系统”的迷宫,里面藏着各种各样的文件和文件夹,它们就像是迷宫中的宝藏。但有时候,这…...
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后台代理服务准备ÿ…...
阿里面试总结 一
写了这些还是不够完整,阿里 字节 卷进去加班!奥利给 ThreadLocal 线程变量存放在当前线程变量中,线程上下文中,set将变量添加到threadLocals变量中 Thread类中定义了两个ThreadLocalMap类型变量threadLocals、inheritableThrea…...
多线程(49)定义无锁、阻塞、非阻塞和无等待算法
在并发编程中,理解不同的同步策略——无锁(Lock-Free)、阻塞(Blocking)、非阻塞(Non-Blocking)、无等待(Wait-Free)——对于设计高效、健壮的多线程应用至关重要。让我们…...
(一)ffmpeg 入门基础知识
一、ffmpeg FFmpeg是一套强大的开源音视频处理工具,能够录制、转换以及流化音视频内容。 FFmpeg是开源的,这意味着它的源代码是公开的,允许任何人使用、修改和分发。它提供了录制、转换以及流化音视频的完整解决方案,支持多种格…...
【软件测试】个人博客系统测试
个人博客系统测试 一、项目背景1.1 技术背景1.2 功能背景 二、 测试用例编写三、自动化测试3.1 什么是自动化测试3.2 通过使用selenium进行自动化测试的编写(Java实现)3.3 编写测试用例,执行自动化测试3.3.1 输入用户名:test,密码:123&#x…...
20240410解决OK3588-C的核心板刷机之后无法启动的问题
20240410解决OK3588-C的核心板刷机之后无法启动的问题 2024/4/10 19:38 1、编译OK3588的LINUX/Buildroot?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行业最热门的话题,它是利用有效的AI模型交互提示技术,引导大语言模型生成更高质量、更准确、更相关的回应。相对于预训练和微调,提示词工程不需要标注数据和训练模型,极大的节约了时间和…...
RuleEngine规则引擎底层改造AviatorScript 之公式规则
前情提要,看上一个文章,具体要实现的效果就是 当然上来的问题就是前端的问题,这个框首先他们用的是富文本,富文本传到后台的结果是前端脚本,带着h5的标签,后面改成了这个,当时这个东西其实和后…...
Vue项目(H5)与微信小程序来回跳转
新建H5页面 在小程序里面新建一个名为H5的文件夹,以及H5页面 H5.WXML <web-view src"{{h5Url}}" bindmessage"handleGetMessage"></web-view>H5.JSdata: { h5Url:https://xxx.com/login 要跳转的H5页面},H5回来的回调方法handleG…...
设计模式-单一职责原则
基本介绍 对类来说的,即一个类应该只负责一项职责。如类A负责两个不同的职责,职责1,职责2.当职责1需求变更而改变A时,可能造成职责2执行错误,所以需要将类A的粒度分解为A1,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开发流程一览
近年来,随着全球化的发展和人们对跨文化交流的需求增加,多语言婚恋交友APP的需求逐渐增长。开发这类APP需要考虑到不同语言和文化下用户的需求,涉及到一系列独特的流程和挑战。本文将从专家角度为您解析多语言婚恋交友APP的开发流程ÿ…...
css实现圆环展示百分比,根据值动态展示所占比例
代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...
理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...
Axios请求超时重发机制
Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式: 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...
UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
Mobile ALOHA全身模仿学习
一、题目 Mobile ALOHA:通过低成本全身远程操作学习双手移动操作 传统模仿学习(Imitation Learning)缺点:聚焦与桌面操作,缺乏通用任务所需的移动性和灵活性 本论文优点:(1)在ALOHA…...
Linux中《基础IO》详细介绍
目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改,实现简单cat命令 输出信息到显示器,你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...
DAY 26 函数专题1
函数定义与参数知识点回顾:1. 函数的定义2. 变量作用域:局部变量和全局变量3. 函数的参数类型:位置参数、默认参数、不定参数4. 传递参数的手段:关键词参数5 题目1:计算圆的面积 任务: 编写一…...
C++--string的模拟实现
一,引言 string的模拟实现是只对string对象中给的主要功能经行模拟实现,其目的是加强对string的底层了解,以便于在以后的学习或者工作中更加熟练的使用string。本文中的代码仅供参考并不唯一。 二,默认成员函数 string主要有三个成员变量,…...
