发布题解

更好的阅读体验?

【题目】

生活在一个 row * col 的矩阵（均不超过 20）的机器人每天要到n个目标点巡视，机器人起始位置坐标为（x ，y），机器人只能沿 x，y 轴移动，不能走对角线，问从起始位置出发，走过每个目标点之后返回到起始位置，最短的路径是多少？

【输入格式】

第一行为一个整数，表示测试数据的组数。 以后每组数据的第一行为两个整数，表示矩阵大小。 第二行为两个整数，即起始位置坐标。 第三行为一个整数即目标点数 n（ n \le 10），随后 n 行为各点坐标，均为整数。

【输出格式】

输出最短路径，每组测试数据一行。

【输入样例】

1
10 10
1 1
4
2 3
5 5
9 4
6 5

【输出样例】

The shortest path has length 24

【算法分析】

这道题的算法最容易想到的是贪心，这是什么意思呢?就是我们寻找最近的巡视的点，统计就好了。 但我们可以发现：它走完全程后是要回到去一开始的起始位置的，所以贪心法是不可行的，举个例子：（0 表示不用走，1 表示要走，2 是起点）

2 1 1 0 1
0 0 0 0 1
0 0 0 1 0
0 0 0 0 0
0 0 0 0 1

如果我们用贪心法解决，走完(2,5)后，我们会先走(3,4),但是正确解法是走(5,5)。

出于数据不大，我们可以用搜索，试遍所有的点。

【参考代码】

int Calc(int ans = 0) {  //计算距离
  for(int i = 0; i < n; i++)
    ans += abs(p[a[i]].x-p[a[i + 1]].x) + abs(p[a[i]].y - p[a[i + 1]].y);
  ans += abs(p[a[n]].x - p[a[0]].x) + abs(p[a[n]].y - p[a[0]].y);
  return ans;
}

void DFS(int k) {  //深搜
  if(k > n)
    Min=min(Min,Calc());  //计算
  else
    for(int i = 1; i <= n; i++)
      if(used[i] == 0) {
        used[i] = 1;  //改值
        a[k] = i;
        DFS(k + 1);  //回溯
        used[i] = 0;
      }
}