4403巡视

4403   巡视

题目描述

典狱长每天要到监狱的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

说明

0
0
通过提交
时空限制1000ms/128mb
题目来源
评测方式在线评测
题目类型qpl
难        度