Leetcode 490时间复杂度分析
来源：7-6 Leetcode 上一个困难的问题
讲武德的年轻人
2022-06-08
bobo老师，我有两个关于lc 490 The Maze的问题。
第一个问题：我看您github上题解中，时间复杂度为O(mn)。直觉上我也能理解，但是如何通过推理得到呢？我的理解是，这道题目本身跟一般的经典BFS不同，因为我们只需要记录当球拐弯时候的点的信息，而中间节点不记录。所以，中间（球不能拐弯）的点可以被访问多次。这时候如何得到O(mn)的时间复杂度呢？
第二个问题：是我根据这个题目引申的。如果此题改为：求从start到destination的最短路径长度（如果不能到达则返回-1），此时的时间复杂度如何分析呢？此时，我的理解是，题目比较像leetcode 1293. Shortest Path in a Grid with Obstacles Elimination，即使拐弯的节点也可能被访问多次。这时候，当球要拐弯的时候，我们不仅需要判断该点是否之前被访问过，还要看当前走过的步数是否小于之前走过的步数。也就是说，每个节点的状态是[row, column, steps]。但是leetcode 1293中，steps的上届是k，所以时间复杂度是O(mnk)，不知这个题目如何分析呢？谢谢您！
1回答
-
1
在最差的情况下,在每个点的位置都遇到了墙,要选择4个方向继续走,所以在最差的情况下,一个点只会访问四次(来到这个点,4个方向都试过了,如果再来一次,随便走哪个方向都重复了)。所以复杂度是 O(m*n*4) = O(m*n) 的。
2
看你怎么定义最短路径。
如果是最少次数“撞墙”，直接 BFS 即可，是 O(m*n) 的，分析同上。
但如果是经过的最少的格子，需要基于整个问题建一个带权图，在每一个“撞墙”的位置计算不同方向下，到下一个“撞墙”的位置经过的格子数。之后，对这个带权图求最短路径，用 Dijkstra，复杂度是 O(mn * log(mn)) 的。（Dijkstra 的时间复杂度）
继续加油！：）
00
相似问题