BoBo老师好，您play-leetcode上的286号问题 Walls and Gates好像代码超时了

Question

BoBo老师您好，您play-leetcode上的286号问题的代码在leetcode上提交时显示Time Limit Exceeded了，请问老师可以帮忙看一下吗？谢谢?

Answer 1

liuyubobobo 2019-06-13 08:58:25

感谢提醒。我重新修改了一下，可以参考这里：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0286-Walls-and-Gates/cpp-0286/main.cpp

之前的算法相当于对每一个room进行一次bfs，所以时间复杂度应该是 room_num * m * n 的。

现在优化后的算法，一上来将所有的gate放入队列。之后从gate的位置开始做bfs，到达了某个room，这个距离就是这个room到某个gate的最短距离：）这个算法的时间复杂度是O(m * n )的：）

继续加油！：）

• 提问者 Ko1231 #1

  老师请问一下，为什么从某个gate开始bfs,到达了一个没有被更新过的room，这个距离就是这个room距离它最近的gate的距离了？为什么不需要将这个距离值和别的gate与这个room的最短距离相比较后取最小值呢？（我的理解是这是这个room距离其中一个gate的最短距离，但是这个gate不一定就是离它最近的gate)

• liuyubobobo 回复 提问者 Ko1231 #2

  因为在队列中，先处理距离为0的room（就是gate，初始化放进去），在处理距离为1的room，再处理距离为2的room，以此类推。来到一个room，他如果被更新过，一定有一个距离更短的门：）找一个测试用例，模拟一下这个过程，再感觉一下？继续加油！：）

• 提问者 Ko1231 回复 liuyubobobo #3

  谢谢BoBo老师～