algorithm - 最大最小曼哈顿距离

Question

输入:

• 一组点
• 坐标是非负的integer类型。
• 整数 k

输出:

点 P(x, y)(在给定集中或不在给定集中)，其到最近的曼哈顿距离最大且 max(x, y) <= k

我的(天真的)解决方案:

For every (x, y) in the grid which contain given set
    BFS to find closest  point to (x, y)
    ...
return maximum;

但我觉得它对于大网格运行起来很慢，请帮我设计一个更好的算法(或代码/伪代码)来解决这个问题。

我是否应该遍历每个 (x, y)？在网格中，只需要循环每个中位数 x, y

P.S:对不起我的英语

编辑:

示例:

给定P1(x1,y1), P2(x2,y2), P3(x3,y3) .查找 P(x,y)这样 min {距离(P，P1)，距离(P，P2)， dist(P,P3)} 是最大的

Answer 1

是的，你可以做得更好。我不确定我的解决方案是否最优，但比你的好。

而不是对网格中的每个点进行单独的 BFS。一次从所有输入点执行“累积”BFS。

你从二维数组 dist[k][k] 开始，如果单元格的输入中有一个点，则单元格初始化为 +inf 和零，然后你尝试从输入中的每个点 P 进入每一个可能的方向。您离起点越远，您放入数组 dist 中的整数就越大。如果 dist 中有一个特定单元格的值，但您可以通过更小的步骤(更小的整数)到达那里，您可以覆盖它。

最后，当不能再移动时，您扫描数组 dist 以找到具有最大值的单元格。这就是你的观点。

我认为这在实践中会很有效。

对于 k = 3，假设 1 <= x,y <= k，P1 = (1,1)，P2 = (1,3)，P3 = (2,2)

dist 一开始是相等的

0, +inf, +inf,

+inf, 0, +inf,

0, +inf, +inf,

下一步将是:

0, 1, +inf,

1, 0, 1,

0, 1, +inf,

下一步将是:

0, 1, 2,

1, 0, 1,

0, 1, 2,

所以输出是 P = (3,1) 或 (3,3)