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

AtCoder AT_abc405_d ABC405D - Escape Route

前言

BFS 算法在 AtCoder 比赛中还是会考的,因为不常练习导致没想到,不仅错误 TLE 了很多,还影响了心态,3 发罚时后才 AC。

思路

首先,我们把所有位置和出口的距离算出来(用 BFS),记为 d x , y d_{x,y} dx,y,顺便求出离它最近的出口坐标,记为 ( X x , y , Y x , y ) (X_{x,y},Y_{x,y}) (Xx,y,Yx,y)。我们发现这个需要在队列里记下这个点的最近出口位置以及具体坐标。

然后我们像涟漪一样扩散着用 BFS 去求方向。找每个位置的上一步,然后判断是否是一条路上的(即最近出口相同且距离大于这个点的距离),如果是,那么修改方向并压入队列,否则忽略。

似乎很成功地做完了,那么有哪些易错点呢?

  • 更新方向的时候一定要注意距离是否大于当前点的距离。注意:必须是严格大于,等于也不可以,因为加上这一步之后就不是最优。
  • 记得把安全疏散出口的最近出口位置设为它自己。
  • 一定要用 BFS,而不是 DFS,两个函数都得用 BFS。

代码

AC 提交记录:Submission #65683293。

TLE 提交记录:第一发、第二发、第三发。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;int h, w, d[1010][1010];
char a[1010][1010];
pair<int, int> p[1010][1010];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
char cc[] = {'v', '^', '>', '<'};void work()
{queue<pair<pair<int, int>, pair<int, int> > > q;for (int x = 1; x <= h; x++)for (int y = 1; y <= w; y++)if (a[x][y] == 'E'){p[x][y] = make_pair(x, y);q.push(make_pair(make_pair(x, y), make_pair(x, y)));d[x][y] = 0;}while (q.size()){int fx = q.front().first.first;int fy = q.front().first.second;int xx = q.front().second.first;int yy = q.front().second.second;q.pop();for (int i = 0; i < 4; i++){int nx = fx + dx[i];int ny = fy + dy[i];if (nx < 1 || nx > h)continue;if (ny < 1 || ny > w)continue;if (a[nx][ny] != '.')continue;if (d[nx][ny] > d[fx][fy] + 1){d[nx][ny] = d[fx][fy] + 1;p[nx][ny] = make_pair(xx, yy);q.push(make_pair(make_pair(nx, ny), make_pair(xx, yy)));}}}
}void calc()
{queue<pair<int, int> > q;for (int x = 1; x <= h; x++)for (int y = 1; y <= w; y++)if (a[x][y] == 'E')q.push(make_pair(x, y));while (q.size()){int fx = q.front().first;int fy = q.front().second;q.pop();for (int i = 0; i < 4; i++){int nx = fx + dx[i];int ny = fy + dy[i];if (nx < 1 || nx > h)continue;if (ny < 1 || ny > w)continue;if (a[nx][ny] != '.')continue;if (p[nx][ny] != p[fx][fy])continue;if (d[nx][ny] <= d[fx][fy])continue;a[nx][ny] = cc[i];q.push(make_pair(nx, ny));}}
}int main()
{cin >> h >> w;for (int i = 1; i <= h; i++)for (int j = 1; j <= w; j++)cin >> a[i][j];memset(d, 0x3f, sizeof(d));work();calc();for (int i = 1; i <= h; i++){for (int j = 1; j <= w; j++)cout << a[i][j];cout << endl;}return 0;
}

相关文章:

AtCoder AT_abc405_d ABC405D - Escape Route

前言 BFS 算法在 AtCoder 比赛中还是会考的&#xff0c;因为不常练习导致没想到&#xff0c;不仅错误 TLE 了很多&#xff0c;还影响了心态&#xff0c;3 发罚时后才 AC。 思路 首先&#xff0c;我们把所有位置和出口的距离算出来&#xff08;用 BFS&#xff09;&#xff0c…...

Redis-x64-3.0.500

E:\Workspace_zwf\Redis-x64-3.0.500 redis.windows.conf...

CUDA编程——性能优化基本技巧

本文主要介绍下面三种技巧&#xff1a; 使用 __restrict__ 让编译器放心地优化指针访存想办法让同一个 Warp 中的线程的访存 Pattern 尽可能连续&#xff0c;以利用 Memory coalescing使用 Shared memory 0. 弄清Kernael函数是Compute-bound 还是 Memory-bound 先摆出一个知…...

图像卷积初识

目录 一、卷积的概念 1、常见卷积核示例 二、使用 OpenCV 实现卷积操作 1、代码说明 2、运行说明 一、卷积的概念 在图像处理中&#xff0c;卷积是一种通过滑动窗口&#xff08;卷积核&#xff09;对图像进行局部计算的操作。卷积核是一个小的矩阵&#xff0c;它在图像上…...

K8S服务的请求访问转发原理

开启 K8s 服务异常排障过程前&#xff0c;须对 K8s 服务的访问路径有一个全面的了解&#xff0c;下面我们先介绍目前常用的 K8s 服务访问方式&#xff08;不同云原生平台实现方式可能基于部署方案、性能优化等情况会存在一些差异&#xff0c;但是如要运维 K8s 服务&#xff0c;…...

VSCode-插件:codegeex:ai coding assistant / 清华智普 AI 插件

一、官网 https://codegeex.cn/ 二、vscode 安装插件 点击安装即可&#xff0c;无需复杂操作&#xff0c;国内软件&#xff0c;无需科学上网&#xff0c;非常友好 三、智能注释 输入 // 或者 空格---后边自动出现注释信息&#xff0c;&#xff0c;按下 Tab 键&#xff0c;进…...

Kubernetes生产实战(十四):Secret高级使用模式与安全实践指南

一、Secret核心类型解析 类型使用场景自动管理机制典型字段Opaque (默认)自定义敏感数据需手动创建data字段存储键值对kubernetes.io/dockerconfigjson私有镜像仓库认证kubelet自动更新.dockerconfigjsonkubernetes.io/tlsTLS证书管理Cert-Manager可自动化tls.crt/tls.keykube…...

【验证码】⭐️集成图形验证码实现安全校验

&#x1f4a5;&#x1f4a5;✈️✈️欢迎阅读本文章❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;本篇文章阅读大约耗时5分钟。 ⛳️motto&#xff1a;不积跬步、无以千里 &#x1f4cb;&#x1f4cb;&#x1f4cb;本文目录如下&#xff1a;&#x1f381;&#x1f381;&am…...

iOS瀑布流布局的实现(swift)

在iOS开发中&#xff0c;瀑布流布局&#xff08;Waterfall Flow&#xff09;是一种常见的多列不等高布局方式&#xff0c;适用于图片、商品展示等场景。以下是基于UICollectionView实现瀑布流布局的核心步骤和优化方法&#xff1a; 一、实现原理 瀑布流的核心在于动态计算每个…...

TGRS | FSVLM: 用于遥感农田分割的视觉语言模型

论文介绍 题目&#xff1a;FSVLM: A Vision-Language Model for Remote Sensing Farmland Segmentation 期刊&#xff1a;IEEE Transactions on Geoscience and Remote Sensing 论文&#xff1a;https://ieeexplore.ieee.org/document/10851315 年份&#xff1a;2025 单位…...

#Redis黑马点评#(四)优惠券秒杀

目录 一 生成全局id 二 添加优惠券 三 实现秒杀下单 方案一&#xff08;会出现超卖问题&#xff09; 方案二&#xff08;解决了超卖但是错误率较高) 方案三&#xff08;解决了错误率较高和超卖但是会出现一人抢多张问题) 方案四&#xff08;解决一人抢多张问题“非分布式…...

https,http1,http2,http3的一些知识

温故知新&#xff0c;突然有人问我项目中&#x1f914;有使用http3么&#xff0c;一下不知从何说起&#xff0c;就有了这篇文章的出现。 https加密传输&#xff0c;ssltls https 验证身份 提供加密&#xff0c;混合加密 &#xff1a; 对称加密 非对称加密 原理&#xff1a…...

《设计数据密集型应用》——阅读小记

设计数据密集型应用 这本书非常推荐看英语版&#xff0c;如果考过了CET-6就可以很轻松的阅读这本书。 当前计算机软件已经不是单体的时代了&#xff0c;分布式系统&#xff0c;微服务现在是服务端开发的主流&#xff0c;如果没有读过这本书&#xff0c;则强力建议读这本书。 …...

SpringCloud之Gateway基础认识-服务网关

0、Gateway基本知识 Gateway 是在 Spring 生态系统之上构建的 API 网关服务&#xff0c;基于 Spring &#xff0c;Spring Boot 和 Project Reactor 等技术。 Gateway 旨在提供一种简单而有效的方式来对 API 进行路由&#xff0c;以及提供一些强大的过滤器功能&#xff0c;例如…...

MySQL 从入门到精通(三):日志管理详解 —— 从排错到恢复的核心利器

在 MySQL 数据库的日常运维中&#xff0c;日志是定位问题、优化性能、数据恢复的核心工具。无论是排查服务器启动异常&#xff0c;还是分析慢查询瓶颈&#xff0c;亦或是通过二进制日志恢复误删数据&#xff0c;日志都扮演着 “数据库黑匣子” 的角色。本文将深入解析 MySQL 的…...

单脉冲前视成像多目标分辨算法——论文阅读

单脉冲前视成像多目标分辨算法 1. 论文的研究目标及实际意义1.1 研究目标1.2 实际问题与产业意义2. 论文的创新方法及公式解析2.1 核心思路2.2 关键公式与模型2.2.1 单脉冲雷达信号模型2.2.2 匹配滤波输出模型2.2.3 多目标联合观测模型2.2.4 对数似然函数与优化2.2.5 MDL准则目…...

SpringBoot项目容器化进行部署,meven的docker插件远程构建docker镜像

需求&#xff1a;将Spring Boot项目使用容器化进行部署 前提 默认其他环境,如mysql,redis等已经通过docker部署完毕, 这里只讨论,如何制作springboot项目的镜像 要将Spring Boot项目使用docker容器进行部署&#xff0c;就需要将Spring Boot项目构建成一个docker镜像 一、手动…...

【金仓数据库征文】政府项目数据库迁移:从MySQL 5.7到KingbaseES的蜕变之路

摘要&#xff1a;本文详细阐述了政府项目中将 MySQL 5.7 数据库迁移至 KingbaseES 的全过程&#xff0c;涵盖迁移前的环境评估、数据梳理和工具准备&#xff0c;迁移实战中的数据源与目标库连接配置、迁移任务详细设定、执行迁移与过程监控&#xff0c;以及迁移后的质量验证、系…...

C++GO语言微服务和服务发现②

01 创建go-micro项目-查看生成的 proto文件 02 创建go-micro项目-查看生成的main文件和handler ## 创建 micro 服务 命令&#xff1a;micro new --type srv test66 框架默认自带服务发现&#xff1a;mdns。 使用consul服务发现&#xff1a; 1. 初始consul服务发现&…...

手机银行怎么打印流水账单(已解决)

一、中国银行 登录中国银行手机银行APP。 在首页点击“更多”&#xff0c;向左滑动找到并点击“助手”。 在助手页面选择“交易流水打印”。 点击“立即申请”&#xff0c;选择需要打印的账户和时间段。 输入接收流水账单的电子邮箱地址。 提交申请后&#xff0c;在“申请…...

单片机-STM32部分:10-2、逻辑分析仪

飞书文档https://x509p6c8to.feishu.cn/wiki/VrdkwVzOnifH8xktu3Bcuc4Enie 安装包如下&#xff1a;根据自己的系统选择&#xff0c;目前这个工具只有window版本哦 安装方法比较简单&#xff0c;都按默认下一步即可&#xff0c;注意不要安装到中文路径哦。 其余部分参考飞书文档…...

Scala与Go的异同教程

当瑞士军刀遇到电锯&#xff1a;Scala vs Go的相爱相杀之旅 各位准备秃头的程序猿们&#xff08;放心&#xff0c;用Go和Scala不会加重你的发际线问题&#xff09;&#xff0c;今天我们来聊聊编程界的"冰与火之歌"——Scala和Go的异同。准备好瓜子饮料&#xff0c;我…...

【算法-哈希表】常见算法题的哈希表套路拆解

算法相关知识点可以通过点击以下链接进行学习一起加油&#xff01;双指针滑动窗口二分查找前缀和位运算模拟链表 在刷题的过程中&#xff0c;我们会频繁遇到一些“高频套路”——而哈希表正是其中最常用也最高效的工具之一。它能帮助我们在 O(1) 的时间复杂度内完成查找、插入与…...

前端取经路——现代API探索:沙僧的通灵法术

大家好,我是老十三,一名前端开发工程师。在现代Web开发中,各种强大的API就像沙僧的通灵法术,让我们的应用具备了超乎想象的能力。本文将带你探索从离线应用到实时通信,从多线程处理到3D渲染的九大现代Web API,让你的应用获得"通灵"般的超能力。 在前端取经的第…...

深入了解 ArkTS:HarmonyOS 开发的关键语言与应用实践

随着 HarmonyOS&#xff08;鸿蒙操作系统&#xff09;的推出&#xff0c;华为为开发者提供了一套全新的开发工具和编程语言&#xff0c;使得跨设备、跨平台的应用开发成为可能。在这些工具中&#xff0c;ArkTS&#xff08;Ark TypeScript&#xff09;作为一种专为 HarmonyOS 设…...

Flask 调试的时候进入main函数两次

在 Flask 开启 Debug 模式时&#xff0c;程序会因为自动重载&#xff08;reloader&#xff09;的机制而启动两个进程&#xff0c;导致if __name__ __main__底层的程序代码被执行两次。以下说明其原理与常见解法。 Flask Debug 模式下自动重载机制 Flask 使用的底层服务器 Wer…...

Git 时光机:修改Commit信息

前言 列位看官都知道&#xff0c;Git 的每一次 git commit&#xff0c;其中会包含作者&#xff08;Author&#xff09;和提交者&#xff08;Committer&#xff09;的姓名与邮箱。有时可能会因为配置错误、切换了开发环境&#xff0c;或者只是单纯的手滑&#xff0c;导致 commi…...

DAY 21 常见的降维算法

知识点回顾&#xff1a; LDA线性判别PCA主成分分析t-sne降维 还有一些其他的降维方式&#xff0c;也就是最重要的词向量的加工&#xff0c;我们未来再说 作业&#xff1a; 自由作业&#xff1a;探索下什么时候用到降维&#xff1f;降维的主要应用&#xff1f;或者让ai给你出题&…...

Docker使用小结

概念 镜像&#xff08; Image &#xff09; &#xff1a;相当于一个 root 文件系统&#xff1b;镜像构建时&#xff0c;分层存储、层层构建&#xff1b;容器&#xff08; Container &#xff09; &#xff1a;镜像是静态的定义&#xff0c;容器是镜像运行时的实体&#xff1b;…...

kubectl top 查询pod连接数

在 Kubernetes 中&#xff0c;kubectl top 命令默认仅支持查看 Pod 或节点的 CPU/内存资源使用情况&#xff0c;并不直接提供 TCP 连接数的统计功能。若要获取 Pod 的 TCP 连接数&#xff0c;需结合其他工具和方法。以下是具体实现方案&#xff1a; 1. 直接进入容器查看 TCP 连…...

Kubernetes生产实战(十七):负载均衡流量分发管理实战指南

在Kubernetes集群中&#xff0c;负载均衡是保障应用高可用、高性能的核心机制。本文将从生产环境视角&#xff0c;深入解析Kubernetes负载均衡的实现方式、最佳实践及常见问题解决方案。 一、Kubernetes负载均衡的三大核心组件 1&#xff09;Service资源&#xff1a;集群内流…...

Git 分支指南

什么是 Git 分支&#xff1f; Git 分支是仓库内的独立开发线&#xff0c;你可以把它想象成一个单独的工作空间&#xff0c;在这里你可以进行修改&#xff0c;而不会影响主分支&#xff08;或 默认分支&#xff09;。分支允许开发者在不影响项目实际版本的情况下&#xff0c;开…...

自动泊车技术—相机模型

一、相机分类及特性 传感器类型深度感知原理有效工作范围环境适应性功耗水平典型成本区间数据丰富度单目相机运动视差/几何先验1m~∞光照敏感1-2W5−5−502D纹理中双目相机立体匹配 (SGM/SGBM算法)0.3m~20m纹理依赖3-5W50−50−3002D稀疏深度多摄像头系统多视角三角测量0.1m~5…...

程序代码篇---esp32视频流处理

文章目录 前言一、ESP32摄像头设置1.HTTP视频流&#xff08;最常见&#xff09;2.RTSP视频流3.MJPEG流 二、使用OpenCV读取视频流1. 读取HTTP视频流2. 读取RTSP视频流 三、使用requests库读取MJPEG流四、处理常见问题1. 连接不稳定或断流2. 提高视频流性能2.1降低分辨率2.2跳过…...

数据结构与算法分析实验12 实现二叉查找树

实现二叉查找树 1、二叉查找树介绍2.上机要求3.上机环境4.程序清单(写明运行结果及结果分析)4.1 程序清单4.1.1 头文件 TreeMap.h 内容如下&#xff1a;4.1.2 实现文件 TreeMap.cpp 文件内容如下&#xff1a;4.1.3 源文件 main.cpp 文件内容如下&#xff1a; 4.2 实现展效果示5…...

深入浅出之STL源码分析2_类模版

1.引言 我在上面的文章中讲解了vector的基本操作&#xff0c;然后提出了几个问题。 STL之vector基本操作-CSDN博客 1.刚才我提到了我的编译器版本是g 11.4.0&#xff0c;而我们要讲解的是STL&#xff08;标准模板库&#xff09;&#xff0c;那么二者之间的关系是什么&#x…...

Docker、Docker-compose、K8s、Docker swarm之间的区别

1.Docker docker是一个运行于主流linux/windows系统上的应用容器引擎&#xff0c;通过docker中的镜像(image)可以在docker中构建一个独立的容器(container)来运行镜像对应的服务&#xff1b; 例如可以通过mysql镜像构建一个运行mysql的容器&#xff0c;既可以直接进入该容器命…...

【Linux】线程的同步与互斥

目录 1. 整体学习思维导图 2. 线程的互斥 2.1 互斥的概念 2.2 见一见数据不一致的情况 2.3 引入锁Mutex(互斥锁/互斥量) 2.3.1 接口认识 2.3.2 Mutex锁的理解 2.3.3 互斥量的封装 3. 线程同步 3.1 条件变量概念 3.2 引入条件变量Cond 3.2.1 接口认识 3.2.2 同步的…...

C++发起Https连接请求

需要下载安装openssl //stdafx.h #pragma once #include<iostream> #include <openssl/ssl.h> #include <openssl/err.h> #include <iostream> #include <string>#pragma comment(lib, "libssl.lib") #pragma comment(lib, "lib…...

Linux 内核链表宏的详细解释

&#x1f527; Linux 内核链表结构概览 Linux 内核中的链表结构定义在头文件 <linux/list.h> 中。核心结构是&#xff1a; struct list_head {struct list_head *next, *prev; }; 它表示一个双向循环链表的节点。链表的所有操作都围绕这个结构体展开。 &#x1f9e9; …...

[架构之美]Spring Boot集成MyBatis-Plus高效开发(十七)

[架构之美]Spring Boot集成MyBatis-Plus高效开发&#xff08;十七&#xff09; 摘要&#xff1a;本文通过图文代码实战&#xff0c;详细讲解Spring Boot整合MyBatis-Plus全流程&#xff0c;涵盖代码生成器、条件构造器、分页插件等核心功能&#xff0c;助你减少90%的SQL编写量…...

游戏引擎学习第270天:生成可行走的点

回顾并为今天的内容定下基调 今天的计划虽然还不完全确定&#xff0c;可能会做一些内存分析&#xff0c;也有可能暂时不做&#xff0c;因为目前并没有特别迫切的需求。最终我们会根据当下的状态随性决定&#xff0c;重点是持续推动项目的进展&#xff0c;无论是 memory 方面还…...

批量统计PDF页数,统计图像属性

软件介绍&#xff1a; 1、支持批量统计PDF、doc\docx、xls\xlsx页数 2、支持统计指定格式文件数量&#xff08;不填格式就是全部&#xff09; 3、支持统计JPG、JPEG、PNG图像属性 4、支持统计多页TIF页数、属性 5、支持统计PDF、JPG画幅 统计图像属性 「托马斯的文件助手」…...

QT Creator配置Kit

0、背景&#xff1a;qt5.12.12vs2022 记得先增加vs2017编译器 一、症状&#xff1a; 你是否有以下症状&#xff1f; 1、用qt新建的工程&#xff0c;用qmake&#xff0c;可惜能看见的只有一个pro文件&#xff1f; 2、安装QT Creator后&#xff0c;使用MSVC编译显示no c com…...

[架构之美]IntelliJ IDEA创建Maven项目全流程(十四)

[架构之美]IntelliJ IDEA创建Maven项目全流程&#xff08;十四&#xff09; 摘要&#xff1a;本文将通过图文结合的方式&#xff0c;详细讲解如何使用IntelliJ IDEA快速创建Maven项目&#xff0c;涵盖环境配置、项目初始化、依赖管理及常见问题解决方案。适用于Java开发新手及…...

SpringBoot学习(上) , SpringBoot项目的创建(IDEA2024版本)

目录 1. SpringBoot介绍 SpringBoot特点 2. SpringBoot入门 2.1 创建SpringBoot项目 Spring Initialize 第一步: 选择创建项目 第二步: 选择起步依赖 第三步: 查看启动类 2.2 springboot父项目 2.3 测试案例 2.3.1 数据库 2.3.2 生成代码 1. SpringBoot介绍 Spring B…...

《Python星球日记》 第51天:神经网络基础

名人说&#xff1a;路漫漫其修远兮&#xff0c;吾将上下而求索。—— 屈原《离骚》 创作者&#xff1a;Code_流苏(CSDN)&#xff08;一个喜欢古诗词和编程的Coder&#x1f60a;&#xff09; 目录 一、引言&#xff1a;走进神经网络的世界二、神经元与激活函数1. 神经元&#x…...

MindSpore框架学习项目-ResNet药物分类-模型评估

目录 4.模型评估 4.1模型预测 4.1.1加载模型 4.1.2通过传入图片路径进行推理 单张图片推理代码解释 4.2图片推理 4.2.1构造可视化推理结果函数 可视化推理结果函数代码解释 4.2.2进行单张推理 参考内容&#xff1a; 昇思MindSpore | 全场景AI框架 | 昇思MindSpore社区…...

Visual Studio Code 前端项目开发规范合集【推荐插件】

文章目录 前言代码格式化工具&#xff08;Prettier&#xff09;1、下载 prettier 相关依赖&#xff1a;2、安装 Vscode 插件&#xff08;Prettier&#xff09;&#xff1a;3、配置 Prettier&#xff08;.prettierrc.cjs&#xff09;&#xff1a; 代码规范工具&#xff08;ESLin…...

uniapp-商城-48-后台 分类数据添加修改弹窗bug

在第47章的操作中&#xff0c;涉及到分类的添加、删除和更新功能&#xff0c;但发现uni-popup组件存在bug。该组件的函数接口错误导致在小程序中出现以下问题&#xff1a;1. 点击修改肉类名称时&#xff0c;回调显示为空&#xff0c;并报错“setVal is not defined”&#xff0…...