如图所示，有一个带有 Homes 和 PowerStations 的二维网格。找出一种算法来为每个家庭找到最近的发电站。 我知道怎么写暴力算法，复杂度为 O(m*n)，其中 m 是家庭的数量，n 是发电站的数量。但是谁能给出更好的解决方案？ (可以假设发电站通常以这种方式定位)
最佳答案
如果您的输入是网格，请执行 BFS。
首先，将所有电站插入队列。然后像往常一样进行 BFS，稍作修改:您必须记住每个添加的方 block 是从哪个初始发电站访问的。
使用此算法，您将自然地到达距离最近的发电站的每栋房子。
复杂度为 O(s^2)。其中 s 是网格的边。
关于在二维网格上寻找发电站的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31632572/