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 20Output
:#1 320推荐阅读
- 如何使用CSS设置div宽度以适合内容（）
- Directi面试问题详细分享
- 算法设计（循环调度算法程序详细实现S1）
- DART和C++之间有什么区别（）
- PHP如何使用date_isodate_set()函数（用法实例）
- 使用Java在原始数组中查找最大值或最小值
- Nodejs使用nodemon自动重启NodeJs服务器
- 给定以十进制为底的数字N，请以任意底数(底为b)查找其位数
- Go语言中的select语句怎么使用（用法示例解析）