作者sean72 (.)
看板Prob_Solve
标题[问题] LC 505 the maze ii 时间复杂度估算
时间Fri Jan 11 12:38:04 2019
Leetcode 505. The Maze II 时间复杂度怎麽计算?
这题锁上了。题目请见这篇：
http://www.cnblogs.com/grandyang/p/6725380.html
leetcde 解法1 每个点不断的暴力更新
https://paste.ubuntu.com/p/mdmfBFFgJf/
每次bfs的时候加一层while loop来模拟滚动 time complexity m*n*max(m,n)
我的理解：总共m*n个点，每个点都有m or n的滚动的可能 (这应该正确吧?)
leetcde 解法2 用一个heap来代替que以实现最短路径
https://paste.ubuntu.com/p/HP5v93dQKf/
我最早的想法：总共m*n个点，heap里面最多就是m*n，
所以每次弹出的复杂度就是log(m*n)
总共m*n个点，所以是m*n*log(m*n)
每次弹出之後有滚动，那麽就变成 m*n*log(m*n)*max(m,n)
(很明显不对，这样就比上面的暴力还慢)
解答上写 m*n*log(m*n) <-- 那麽每一个点弹出之後的滚动呢？
谢谢大家的回答
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 73.189.14.17
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1547181489.A.0B2.html
※ sean72:转录至看板 Programming 01/11 12:39
※ 编辑: sean72 (73.189.14.17), 01/11/2019 14:25:17
1F：推 FRAXIS: 你顶多只有 m*n 个点 m*n*4 条边 所以你顶多插入 m*n*4 次 01/12 11:40
谢谢你的推文，但我还是不太明白，可以麻烦你再解释多一些吗?
计算用heap
但是每次弹出一个点之後，都需要用while loop滚动，这部分怎麽加入估算呢?
※ 编辑: sean72 (73.189.14.17), 01/12/2019 16:16:50
2F：推 FRAXIS: 你滚动的那部份应该可以作 preprocess 吧 01/12 22:59
该如何做preprocess呢?
谢谢
※ 编辑: sean72 (73.189.14.17), 01/13/2019 09:44:31
3F：推 FRAXIS: 一个简单的方法 就是先把 Graph 直接建起来 01/14 05:40
4F：→ FRAXIS: 每一个点 可以滚动到哪些点 在搜寻之前先建好 01/14 05:40
5F：→ FRAXIS: 在建的时候要有技巧 因为点 u 朝方向 d 最终滚到 v 的话 01/14 05:41
6F：→ FRAXIS: 那 u ~ v 上面的所有点 向 d 滚动必定也都会滚到 v 01/14 05:41
7F：→ FRAXIS: 利用这个性质就可以避免重复计算 01/14 05:42
8F：→ FRAXIS: 然後在搜寻的时候就可以不用计算滚动了 01/14 05:42
9F：→ FRAXIS: 要加速的话 就一边搜寻一边建图 01/14 05:43
10F：→ FRAXIS: 或是用 A* 搜寻，这种 2D Grid Graph 的 Heuristic 01/14 05:44
11F：→ FRAXIS: 已经有很多人研究过了 01/14 05:44