cf 442 D. Olya and Energy Drinks
2024-10-21 06:34:36
cf 442 D. Olya and Energy Drinks(bfs)
题意：
给一张\(n \times m(n <= 1000,m <= 1000)\)的地图
给出一个起点和终点，每秒钟可以沿着四个方向直走\(1\)到$k(k <= 1000) $步,问从起点到终点最少需要多少秒
思路：
最暴力的\(bfs\)时间复杂度为\(O(n * m * k)\)
由bfs可以知道，每个点只需要被访问过一点就已经是最短了，也即访问过一次就可以将其从地图中删去了
- 这里有两种方法可以来实现
1、用set来维护每行每列的点，从set中查找出当前点四个方向最近的点 判断距离是否超过k，更新完之后再从set中删点
这样的时间复杂度为\(O(n * m * log(n))\)
2、用并查集缩点来维护四个方向上最近的未更新过的点 复杂度会比第一种低一些
我们知道每个点只可能被四个方向更新，那么我们用状压维护每个点是被哪些方向更新的
从当前点开始更新某个方向上的点，如果更新的点在这个方向上已经更新过了，显然就可以跳出更新了，因为这个方向上后面的点一定也更新过了。复杂度\(O(4 * n * m)\)
最新文章
- QString 和std::string互转
- Java垃圾收集算法介绍
- 高德地图API应用
- [codevs1073]家族
- 阿里云OSS存储开发（一）
- 【COGS1049】天空中的繁星
- 交叉编译：cannot find /lib/libc.so.6 collect2: ld returned 1 exit status
- linux内核参数调优,缓冲区调整,tcp/udp连接管理,保持,释放优化,gossary,terms
- evernote
- [补档][Hnoi2013]游走
- (转)sizeof()和_countof()区别
- 磁盘IO的性能指标 阻塞与非阻塞、同步与异步 I/O模型
- RPA简介
- shell脚本：通过域名获取证书的过期时间
- Java通过BCrypt加密
- GIS案例学习笔记-明暗等高线提取地理模型构建
- jQuery 向另一个页面传参，同时跳转到该页面
- 第09章：MongoDB-CRUD操作--文档--修改--update
- IDEA的强大
- 数据库与sql注入的相关知识