三星研发中心面试问题

X先生必须向N个客户交付软件。他将从办公室拜访所有客户, 然后返回他的办公室。办公室和客户的每个位置均以整数坐标(x, y)(-1 <x <500, -1 <y <500)的形式给出。通过| x1-x2 |计算两个任意位置(x1, y1)和(x2, y2)之间的距离。 + | y1-y2 |, 其中| x |表示x的绝对值；例如| 3 | = | -3 | = 3。办公室和客户的位置都不同。你应该计划一个最佳的方式来拜访所有N个客户并返回他的办公室。

你将获得办公室和客户的位置；客户数量在1到100的范围内。编写一个程序, 从办公室开始, 找到一条访问所有客户并返回办公室的最短路径。你的程序只需报告最短路径的距离。

[限制条件]

1 <N <100。每个位置(x, y)在有界网格中, -1 <x <500, -1 <y <500, 并且x, y是整数。

[输入]

每个测试用例由两行组成；第一行包含N, 表示客户数量, 下一行依次列出了办公室和客户的位置。每个位置均包含坐标(x, y), 以" x y"表示。

[输出]

每条线输出最短路径的距离。每行看起来像" #x答案", 其中x是测试用例的索引。 " #x"和"答案"之间用空格隔开。

例子：

Input : 
In the first test case, the locations of the office are (0, 0) and the locations of the customers are (70, 40), (30, 10), (10, 5), (90, 70), (50, 20).

5 (Starting test case #1)
0 0 70 40 30 10 10 5 90 70 50 20
Output :
#1 320