小编Jos*_*rns的帖子

对于我学校的ACM-ICPC团队,我们一直难以理解如何解决这个特定的练习问题:

给定位于坐标(X {i},Y {i})的N个节点,计算从节点1,2,3,...,N遍历然后返回到1(按此顺序)所需的最短曼哈顿距离.您只能访问每个节点一次.如果这样的路径不存在,则输出-1.
N由[1,100]
界定X和Y坐标以[1,100,000,000]为界

我们提出了一些样本数据:

N = 4
坐标:
1.(2,2)
2.(2,4)
3.(2,1)
4.(1,3)

在这种情况下,最短路径是从节点1到节点2的12:2单位,从节点2到节点3的5个单元(绕过节点1,在路上),从节点3到节点4的3个单元,然后2个单位返回节点1.

虽然它可能是哈密顿循环.我还认为构建"图形"是问题的主要部分.一旦构建了图形,您就可以走它以找出总体最短距离.我的问题是检测从i到i + 1的路径是否包含一个节点,如果有,那么绕过它的最佳方法是什么(知道重新路由可能还有一个节点)？

更新:我有O(N ^ 2)代码来检测2个节点是否在同一行,诊断或列中,但我不知道重新路由它的方法是什么.

这是我要发布的完整标题,但它恰好太长了:

给定源节点,dest节点和中间节点,如何检测中间节点是否阻塞了最短的曼哈顿距离？

我画了一个图表,使其更清晰.在左侧,"u"是源节点,"v"是目标节点.标记为1到6的节点是中间节点.距离u - > v的最短曼哈顿距离为12,但中间节点形成阻挡它的墙.右边的图表以u'为源,v'为目的地,表明中间节点1到5不会阻止从u'到v'的最短曼哈顿距离.

我正在尝试找到一种不需要我实际进行图搜索(例如BFS)的算法,因为u和v之间的距离可能非常大.