棋盘(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的开发流程ÿ…...
免费Windows桌面分区工具NoFences:3分钟打造高效工作空间
免费Windows桌面分区工具NoFences:3分钟打造高效工作空间 【免费下载链接】NoFences 🚧 Open Source Stardock Fences alternative 项目地址: https://gitcode.com/gh_mirrors/no/NoFences 还在为杂乱无章的Windows桌面而烦恼吗?NoFen…...
Illustrator智能对象替换引擎:企业级设计自动化的技术杠杆
Illustrator智能对象替换引擎:企业级设计自动化的技术杠杆 【免费下载链接】illustrator-scripts Adobe Illustrator scripts 项目地址: https://gitcode.com/gh_mirrors/il/illustrator-scripts 技术价值宣言 在数字设计工业化时代,品牌资产管理…...
使用Taotoken后模型API调用的延迟与稳定性实际体验观察
🚀 告别海外账号与网络限制!稳定直连全球优质大模型,限时半价接入中。 👉 点击领取海量免费额度 使用Taotoken后模型API调用的延迟与稳定性实际体验观察 作为一名日常需要调用多种大模型API的开发者,将多个供应商的接…...
AI时代就业真相:小白程序员如何抓住大模型机遇,收藏这份必看指南!
智联招聘数据显示,AI短期内替代部分岗位,但新增岗位同样显著。编辑、翻译等白领岗位需求缩减,而AI工程师、数据标注师等需求激增。初级职位衰减,中级与高级职位增长,企业招聘更看重软技能与AI应用能力。建议关注新质生…...
技术乐观主义与悲观主义:我们正在走向乌托邦还是dystopia?
测试者的双重身份作为一名软件测试从业者,我们天然地同时拥有两副眼镜:一副是信任的眼镜,相信系统能够按照预期运行,相信缺陷终将被发现和修复;另一副是怀疑的眼镜,习惯于在任何看似完美的流程中寻找裂缝&a…...
SRWE:Windows窗口实时编辑器的专业应用指南
SRWE:Windows窗口实时编辑器的专业应用指南 【免费下载链接】SRWE Simple Runtime Window Editor 项目地址: https://gitcode.com/gh_mirrors/sr/SRWE 在数字内容创作和游戏开发领域,分辨率限制常常成为技术瓶颈。传统Windows窗口管理系统缺乏灵活…...
智能体集成德国铁路实时信息:无需API的Node.js工具箱openclaw-bahn详解
1. 项目概述:一个为智能体打造的德国铁路工具箱如果你经常在德国乘坐火车,或者像我一样,需要为一些自动化流程(比如智能体)集成实时交通信息,那么你肯定对德国铁路(Deutsche Bahn, DB࿰…...
OpenClaw-Readwise:开源高亮同步工具的设计与实现
1. 项目概述:一个连接知识碎片的“机械爪” 如果你和我一样,是个重度阅读爱好者,并且习惯把在各种地方(比如Kindle、网页文章、PDF文档)看到的好句子、有启发的段落,用高亮(Highlightÿ…...
基于MCP协议与向量检索,为AI编程助手构建跨会话持久记忆
1. 项目概述:为AI编程助手构建持久记忆如果你和我一样,日常重度依赖Cursor、Claude Code、Windsurf这类AI编程助手,那你一定遇到过这个让人头疼的场景:昨天在Cursor里花了半小时跟AI解释清楚了一个复杂模块的业务逻辑和设计思路&a…...
PostgreSQL COPY命令实战:从CSV导入到导出的完整数据流处理
1. 为什么你需要掌握COPY命令 如果你经常需要把Excel表格或CSV文件的数据导入PostgreSQL数据库,或者反过来把数据库查询结果导出成文件,那么COPY命令就是你的瑞士军刀。我见过太多人还在用Python脚本逐行读写CSV,不仅效率低,代码还…...
