巡视
成绩 | 100 | 开启时间 | 2016年05月22日 星期日 18:05 |
折扣 | 0.8 | 折扣时间 | 2016年05月22日 星期日 18:05 |
允许迟交 | 是 | 关闭时间 | 2016年05月22日 星期日 18:05 |
输入文件 | Patrol.in | 输出文件 | Patrol.out |
【题目描述】巡视(Patrol.cpp/c/pas)POJ 2907
典狱长每天要到监狱的n个地方巡视一番,监狱可以看作是一个row×col的矩阵(均不超过20),典狱长起点的位置(x,y),还有其他n个目标点,问从起点出发,走过每个目标点之后返回到起点,典狱长只能沿x,y轴移动,不能走对角线,请问最短的路径是多少?
【输入格式】
第一行为一个整数,表示测试数据的组数。以后每组数据的第一行为两个整数,表示矩阵大小,第二行为起始位置坐标,第三行为一个整数即目标点数n,随后n行为各点坐标。
【输出格式】
输出最短路径,每组测试数据一行。
【输入样例】
1(表示测试数据组数)
10 10(表示矩阵大小)
1 1(起始位置)
4 (目标点数)
2 3 (各目标点坐标)
5 5
9 4
6 5
【输出样例】
The shortest path has length 24