<分区>
有一个组织为 NxN 房间的博物馆。部分房间上锁且无法进入。其他房间是开放的，有的房间有看守。守卫只能向北、向南、向东和向西移动，只能穿过开放的房间，并且只能在博物馆内移动。对于每个房间，找到到 guard 的最短距离。你的算法的时间复杂度是多少？
<分区>
有一个组织为 NxN 房间的博物馆。部分房间上锁且无法进入。其他房间是开放的，有的房间有看守。守卫只能向北、向南、向东和向西移动，只能穿过开放的房间，并且只能在博物馆内移动。对于每个房间，找到到 guard 的最短距离。你的算法的时间复杂度是多少？
最佳答案
首先，考虑一种相对简单的方法。
以每个守卫G作为房间集合中的一个顶点，R=N*N，相邻房间之间的可能路径(边)E。
如果必须知道所有房间的最小距离，则从每个 guard 到每个房间的 BFS。
这应该需要时间G * (R+E)，或者类似G*(N*N+E)，或者G*(N *N).
这当然可以通过内存来优化，因为每个 BFS 都会重复计算已经完成的子树。根据房间配置，这可以大大降低上述时间复杂度中的 G。不过，我敢肯定一定有比这更好的东西。
关于algorithm - 采访 : Find shortest path to few elements，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3326945/