Maze II 时间复杂度问题

今天做到锂扣505， 写了一下BFS和DFS两种方法，思路还是比较直观的。但在分析时间复杂度的时候，给绕进去了。参考了discussion里的相关解释，还是一头雾水。（这题跟Maze I不一样，mazeI只需要知道可不可达，所以每个wall 只需要访问一次）
O(m*n) 一般是不考虑寻找neighbor节点的复杂度 (m,n 为数列的行数和列数)。在每个当前节点，寻找neighbor需要max(m,n)。我疑惑的地方在这里：
1. m*n 为什么是worst case需要遍历的节点数？对某一个当前节点cur来说，从四个方向确认了邻居后，向queue中依次放入。worst case是不是，先放入queue中的节点, 恰好是从原点最远的距离。比如总共有x个path到达这个节点，但我们放入queue的顺序，恰好是距离远的path 先放入。那么，我们其实需要对它，进行x次further processing。比如，对它的下一个邻居节点，进行x次更新。当然distance矩阵也要做x次更新。

这种情况下，怎么计算时间复杂度呢？应该不是O(m*n)了

2. 寻找邻居节点的复杂度。如果单独考虑这块，那四个方向，最大的search深度是Max(m, n)。有人说，这个其实可以优化，分别对矩阵扫描4次，就能得到了。这个确实的。但在BFS或dfs的代码实现中，我们并没用采取这种优化方式呀。所以，每个当前节点寻找4个方向的邻居，还是4*m*n 吧。

不知道自己是不是哪个地方理解错了，求指教，求解惑~~ 多谢各位啦！

rexue70 发表于 2018-9-16 06:15
我的理解是如果这个matrix是个大风车的样子，就是说有一环一环的墙，起点在外面必须绕圈圈才能进去找到中心 ...

谢谢你的回复，不过我还是没太看懂，
比如下面这个例子，起点在右上角。紫色和绿色路径都能到达cell[1][2], 但如果紫色路径先被check的话，就要对cell[1][2]做2次dfs.如果存在更多的路径，那相应的需要多次对同一个节点做dfs。那么，应该如何计算这种情况下，visit的节点个数（或次数呢）？为什么是m * n 或 m/2 * n /2呢？如果用priorityQueue(dijkstra)，我能理解，每次肯定先check的肯定是最短路径。

rexue70 发表于 2018-9-17 01:52
我的想法是BFS和DFS都判断了是否更短路径之后才往下走的，distance[s[0]][s[1]] + count < distance[x -  ...

我觉得这道题的BFS跟普通的BFS不一样的地方就在于，先放入queue中的不一定是最短的路径，比如例子里的紫色路径很可能先放入queue中，那么放入顺序，cell[1][2]就会先被dfs一次。第二次有了一个更短的路径，又会被dfs一次。这题跟minimal flight cost类似，不用priorityqueue的话，每个节点有可能被多次check。

杏树上的杏子 发表于 2018-9-16 08:20
谢谢你的回复，不过我还是没太看懂，
比如下面这个例子，起点在右上角。紫色和绿色路径都能到 ...

你的例子两个路径都到了[1][2]点，然后从[1][2]点出发，最多可以做max(m, n)的距离。然后一共有m*n个点，虽然你在到达[1][2]之前cover的很多点而且没有停，但是不保证之后的路线可能绕圈圈又绕回来了。worst case我们考虑每一个点都是类似[1][2]点的情况。最后T(n) = O(mn * max(m, n))

我的理解是如果这个matrix是个大风车的样子，就是说有一环一环的墙，起点在外面必须绕圈圈才能进去找到中心的target的话，我们走过了(n / 2) * (m / 2) 个点，单次最远扫描长度max(m, n), 最终时间复杂度不变 T(n) = O(mn * max(m, n))

这题直接上Dijkstra吧，T(n) = O(mn*log(mn))

rexue70 发表于 2018-9-16 11:55
你的例子两个路径都到了[1][2]点，然后从[1][2]点出发，最多可以做max(m, n)的距离。然后一共有m*n个点， ...

谢谢啦！我之前一直纠结为啥一共有m*n个要visit的点（即转折点，墙或边缘）。我给的例子里，两个路径到[1][2]，那么[1][2]需要做2次dfs，对吧？如果每个转折点都有多个路径到达，那么visit的店数会不会大于m*n(包括重复visit的点数)？我怀疑自己的问题是不是跑偏了？

杏树上的杏子 发表于 2018-9-17 01:12
谢谢啦！我之前一直纠结为啥一共有m*n个要visit的点（即转折点，墙或边缘）。我给的例子里，两个路径到[1 ...

我的想法是BFS和DFS都判断了是否更短路径之后才往下走的，distance[s[0]][s[1]] + count < distance[x - dir[0]][y - dir[1]]。[1][2]点有2个路径到达，但是再往下只有一个最短路径继续。每覆盖一个点，只留下一种情况继续。(中间不停的点不算覆盖的点)

杏树上的杏子 发表于 2018-9-17 04:15
我觉得这道题的BFS跟普通的BFS不一样的地方就在于，先放入queue中的不一定是最短的路径，比如例子里的紫 ...

有道理。比较了一下code我才发现dijkstra和bfs区别只有一行，就是q的type不一样。

rexue70 发表于 2018-9-17 05:06
有道理。比较了一下code我才发现dijkstra和bfs区别只有一行，就是q的type不一样。

是的，pq可以保证每次check的都是最短路径到达的，所以不存在bfs多次check同一节点的问题。所以，我不太清楚怎么分析bfs的时间复杂度~~ 希望有思路的童鞋给点提示呀~~：-）

杏树上的杏子 发表于 2018-9-17 06:06
是的，pq可以保证每次check的都是最短路径到达的，所以不存在bfs多次check同一节点的问题。所以，我不太 ...

你给力例子好像和题目不太符合啊。在题目中没办法在空的位置停下来。如果考虑成四边形两边都可以到的同一个位置的话，最大应该是有O(m + n)次dfs到达同一位置，但是由于matrix的结构，能都停或者都绕圈圈，max(m, n)应该算一个upper bound