【游戏——BFS+分层图】
题目
分析
但凡是最优方案可能需要访问同一个点的情况,都需要应用“拆点”,或者说分层图的技巧。多出来的维度主要是区分同一个点的不同状态而用。
对于本题,访问的时机便是一个区分点。
对于类似题“AB路线”,同一个K段的位置是一个区分点(不会跨越一个K段,不然不是最优)。
代码
#include <bits/stdc++.h>
using namespace std;const int N = 110;
const int M = 310;int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};struct node
{int x, y, t;
};int l[N][N], r[N][N];
int dist[N][N][M];
bool st[N][N];
int n, m, t;int bfs()
{memset(dist, 0x3f, sizeof dist);queue<node> q;q.push({1, 1, 0});dist[1][1][0] = 0;while(q.size()){auto u = q.front(); q.pop();for(int i = 0; i < 4; i++){int x = u.x + dx[i];int y = u.y + dy[i];if(x < 1 || y < 1 || x > n || y > m) continue;if(dist[x][y][u.t+1] > u.t + 1 && (u.t + 1 < l[x][y] || u.t + 1 > r[x][y])){if(x == n && y == m) return u.t + 1;dist[x][y][u.t+1] = u.t + 1;q.push({x, y, u.t+1});}}}return -1;
}int main()
{scanf("%d%d%d", &n, &m, &t);for(int i = 1; i <= t; i++){int x, y, a, b;scanf("%d%d%d%d", &x, &y, &a, &b);l[x][y] = a, r[x][y] = b;}printf("%d", bfs());
}
类似题
AB路线——BFS+分层图-CSDN博客
相关文章:
【游戏——BFS+分层图】
题目 分析 但凡是最优方案可能需要访问同一个点的情况,都需要应用“拆点”,或者说分层图的技巧。多出来的维度主要是区分同一个点的不同状态而用。 对于本题,访问的时机便是一个区分点。 对于类似题“AB路线”,同一个K段的位置是…...
SSL 证书是 SSL 协议实现安全通信的必要组成部分
SSL证书和SSL/TLS协议有着密切的关系,但它们本质上是不同的概念。下面是两者的区别和它们之间的关系的表格: 属性SSL/TLS 协议SSL证书英文全称SSL(Secure Sockets Layer),TLS(Transport Layer Security&am…...
Spring 源码硬核解析系列专题(七):Spring Boot 与 Spring Cloud 的微服务源码解析
在前几期中,我们从 Spring 核心的 IoC、AOP、事务管理,到 Spring Boot 的自动装配,逐步揭示了 Spring 生态的底层原理。随着微服务架构的流行,Spring Boot 结合 Spring Cloud 成为了构建分布式系统的主流选择。本篇将深入 Spring Cloud 的核心组件,以服务注册与发现(Eure…...
嵌入式开发:傅里叶变换(5):STM32和Matlab联调验证FFT
目录 1. MATLAB获取 STM32 的原始数据 2. 将数据上传到电脑 3. MATLAB 接收数据并验证 STM32进行傅里叶代码 结果分析 STM32 和 MATLAB 联调是嵌入式开发中常见的工作流程,通常目的是将 STM32 采集的数据或控制信号传输到 MATLAB 中进行实时处理、分析和可视化…...
C# 根据Ollama+DeepSeekR1开发本地AI辅助办公助手
在上一篇《访问DeepSeekR1本地部署API服务搭建自己的AI办公助手》中,我们通过通过Ollama提供的本地API接口用Python实现了一个简易的AI办公助手,但是需要运行Py脚本,还比较麻烦,下面我们用C#依据Ollama提供的API接口开发一个本地A…...
洛谷 P8705:[蓝桥杯 2020 省 B1] 填空题之“试题 E :矩阵” ← 卡特兰数
【题目来源】 https://www.luogu.com.cn/problem/P8705 【题目描述】 把 1∼2020 放在 21010 的矩阵里。要求同一行中右边的比左边大,同一列中下边的比上边的大。一共有多少种方案? 答案很大,你只需要给出方案数除以 2020 的余数即可。 【答案提交】 …...
我的AI工具箱Tauri版-FluxCharacterGeneration参考图像生成人像手办(Flux 版)
本教程基于自研的AI工具箱Tauri版进行ComfyUI工作流FluxCharacterGeneration参考图像生成人像手办(Flux 版)。 我的AI工具箱Tauri版 - FluxCharacterGeneration参考图像生成人像手办(Flux版) 基于先进的FLUX模型,通过…...
DeepSeek开源周Day2:DeepEP - 专为 MoE 模型设计的超高效 GPU 通信库
项目地址:https://github.com/deepseek-ai/DeepEP 开源日历:2025-02-24起 每日9AM(北京时间)更新,持续五天 (2/5)! 引言 在大模型训练中,混合专家模型(Mixture-of-Experts, MoE)因其动…...
51单片机-串口通信编程
串行口工作之前,应对其进行初始化,主要是设置产生波特率的定时器1、串行口控制盒中断控制。具体步骤如下: 确定T1的工作方式(编程TMOD寄存器)计算T1的初值,装载TH1\TL1启动T1(编程TCON中的TR1位…...
python实现基于文心一言大模型的sql小工具
一、准备工作 注册与登录: 登录百度智能云千帆控制台,注册并登录您的账号。 创建千帆应用: 根据实际需求创建千帆应用。创建成功后,获取AppID、API Key、Secret Key等信息。如果已有千帆应用,可以直接查看已有应用的AP…...
deepseek 导出导入模型(docker)
前言 实现导出导入deepseek 模型。deepseek 安装docker下参考 docker 导出模型 实际生产环境建议使用docker-compose.yml进行布局,然后持久化ollama模型数据到本地参考 echo "start ollama" docker start ollama#压缩容器内文件夹,然后拷贝…...
前言:什么是大模型微调
一、大模型微调的基础知识 1. 什么是大模型微调? 大模型微调(Fine-tuning)是指在预训练模型的基础上,针对特定的任务或数据集进行进一步训练的过程。预训练模型通常在大规模的通用数据上训练,具备广泛的语言理解和生…...
TCPDF 任意文件读取漏洞:隐藏在 PDF 生成背后的危险
在网络安全的世界里,漏洞就像隐藏在黑暗中的“定时炸弹”,稍有不慎就会引发灾难性的后果。今天,我们要聊的是一个与 PDF 生成相关的漏洞——TCPDF 任意文件读取漏洞。这个漏洞可能让攻击者轻松读取服务器上的敏感文件,甚至获取整个…...
unity学习53:UI的子容器:面板panel
目录 1 UI的最底层容器:canvas 1.1 UI的最底层容器:canvas 1.2 UI的合理结构 2 UI的子容器:面板panel 2.1 创建panel 2.2 面板的本质: image ,就是一个透明的图片,1个空容器 3 面板的属性 4 面板的…...
水环境水质在线监测系统解决方案
在当今社会,水资源作为人类生存和发展的基础性资源,其质量的优劣直接关系到生态平衡、人类健康以及社会经济的可持续发展。然而,随着工业化、城市化的快速推进,各类污染物不断排入水体,导致水环境面临严峻挑战。水环境…...
HBuilder X中,uni-app、js的延时操作及定时器
完整源码下载 https://download.csdn.net/download/luckyext/90430165 在HBuilder X中,uni-app、js的延时操作及定时器可以用setTimeout和setInterval这两个函数来实现。 1.setTimeout函数用于在指定的毫秒数后执行一次函数。 例如, 2秒后弹出一个提…...
BigDecimal线上异常解决方案:避免科学计数法输出的坑
文章目录 问题背景为什么BigDecimal会输出科学计数法?线上异常场景场景1:数据传递异常场景2:日志记录异常场景3:数据存储异常 解决方案1. 使用toPlainString()方法2. 设置格式化输出3. 自定义工具类 代码示例总结 在Java开发中&am…...
【C语言】指针笔试题
前言:上期我们介绍了sizeof与strlen的辨析以及sizeof,strlen相关的一些笔试题,这期我们主要来讲指针运算相关的一些笔试题,以此来巩固我们之前所学的指针运算! 文章目录 一,指针笔试题1,题目一…...
深入理解Redis:数据类型、事务机制及其应用场景
在当今快速发展的技术领域中,Redis作为一种高性能的内存数据库,已经被广泛应用于各种场景,从简单的缓存实现到复杂的数据处理任务。其灵活性和高效性主要来源于对多种数据结构的支持以及强大的功能特性,如事务处理、持久化选项、高…...
RGMII(Reduced Gigabit Media Independent Interface)详解
一、RGMII的定义与作用 RGMII(精简版千兆介质无关接口)是一种用于千兆以太网(1Gbps)的高效接口标准,旨在减少传统GMII接口的引脚数量,同时保持相同的传输速率。其核心作用包括: 减少引脚数量&a…...
STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...
2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面
代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http…...
《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...
前端开发面试题总结-JavaScript篇(一)
文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包(Closure)?闭包有什么应用场景和潜在问题?2.解释 JavaScript 的作用域链(Scope Chain) 二、原型与继承3.原型链是什么?如何实现继承&a…...
JDK 17 新特性
#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的ÿ…...
SQL慢可能是触发了ring buffer
简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...
Ubuntu系统多网卡多相机IP设置方法
目录 1、硬件情况 2、如何设置网卡和相机IP 2.1 万兆网卡连接交换机,交换机再连相机 2.1.1 网卡设置 2.1.2 相机设置 2.3 万兆网卡直连相机 1、硬件情况 2个网卡n个相机 电脑系统信息,系统版本:Ubuntu22.04.5 LTS;内核版本…...
【安全篇】金刚不坏之身:整合 Spring Security + JWT 实现无状态认证与授权
摘要 本文是《Spring Boot 实战派》系列的第四篇。我们将直面所有 Web 应用都无法回避的核心问题:安全。文章将详细阐述认证(Authentication) 与授权(Authorization的核心概念,对比传统 Session-Cookie 与现代 JWT(JS…...
用js实现常见排序算法
以下是几种常见排序算法的 JS实现,包括选择排序、冒泡排序、插入排序、快速排序和归并排序,以及每种算法的特点和复杂度分析 1. 选择排序(Selection Sort) 核心思想:每次从未排序部分选择最小元素,与未排…...
SDU棋界精灵——硬件程序ESP32实现opus编码
一、 音频处理框架 该项目基于Espressif的音频处理框架构建,核心组件包括 ESP-ADF 和 ESP-SR,以下是完整的音频处理框架实现细节: 1.核心组件 (1) 音频前端处理 (AFE - Audio Front-End) main/components/audio_pipeline/afe_processor.c功能: 声学回声…...
