题目

题目描述：
我们把房间按照笛卡尔坐标系进行建模之后，每个点就有了一个坐标。
假设现在房子里有些纸片需要被收集，收集完纸片你还要回归到原来的位置，你需要制定一个策略来使得自己行走的距离最短。
你只能沿着 x 轴或 y 轴方向移动，从位置 (i,j) 移动到相邻位置 (i+1,j)，(i-1,j)，(i,j+1) 或 (i,j-1) 距离增加 1。

输入描述：
在第一行中给出一个T，1≤T≤10, 代表测试数据的组数。
对于每组输入，在第一行中给出房间大小，第二行给出你的初始位置。
接下来给出一个正整数 n，1≤n≤10 代表纸片的个数。
接下来 n 行，每行一个坐标代表纸片的位置。
保证房间小于20×20，纸片一定位于房间内。

输出描述：
对于每组输入，在一行中输出答案。
格式参见样例。

解析

这道题由于我并没有想到什么办法，我就把所有的点的情况都枚举了一遍。
  • 因为数据量较小，我们这里的枚举方法就是把这些点全排列一遍。我们这里阔以用到STL的全排列函数next_permutation。
  • 时间复杂度O(n!)很大很大，但nb的方法我不会啊。

next_permutation：
  • 这个STL的库函数的作用就是将当前序列到其全排列的下一种情况。与之相对的还有pre_permutation（上一种情况）。

操作：
  1. 这里操作很简单，我们就用一个字符串来做全排列。我们先记录下起始情况就结束情况，这样start == end的时候自然而然的就出来了。
  2. 然后里面按顺序循环遍历计算路程。
  3. 最后选出最小的答案输出来就好了。

打代码咯：
  1. 先保存所有要保存的变量。这里我们可以将起始点作为数组的0位置（方便计算）。
  2. 然后就是全排列查找最小情况。
  3. 输出来就好了，看我代码咯~

AC代码 

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std; 
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 
//代码预处理区 

const int INF = 0x3f3f3f3f;
const int MAX = 17; 
struct Node {
    int x, y;
} paper[MAX];
//全局变量区 

int main() { 
    IOS;
    // freopen("in.txt", "r", stdin);
    int T; cin >> T;
    while (T--) {
        int high, width; cin >> high >> width;
        cin >> paper[0].x >> paper[0].y;
        int n; cin >> n;
        string s, e;
        for (int i = 1; i <= n; i++) {
            cin >> paper[i].x >> paper[i].y;
            s += i + '0';
            e += n - i + 1 + '0';
        }
        s = '0' + s; e = '0' + e;
        int ans = INF;
        while (s != e) {
            int sum = 0;
            for (int i = 1; i <= n; i++) {
                int u = s[i - 1] - '0', v = s[i] - '0';
                sum += abs(paper[v].x - paper[u].x) + abs(paper[v].y - paper[u].y);
            }
            int u = s[n] - '0', v = s[0] - '0';
            sum += abs(paper[v].x - paper[u].x) + abs(paper[v].y - paper[u].y);
            ans = min(ans, sum);
            next_permutation(s.begin() + 1, s.end());
        }
        cout << "The shortest path has length " << ans << endl;
    }
    return 0; 
}
//函数区