【牛客算法周周练7】A-收集纸片

---

题目

---

题目描述：
我们把房间按照笛卡尔坐标系进行建模之后，每个点就有了一个坐标。
假设现在房子里有些纸片需要被收集，收集完纸片你还要回归到原来的位置，你需要制定一个策略来使得自己行走的距离最短。
你只能沿着 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，纸片一定位于房间内。
对于每组输入，在一行中输出答案。
格式参见样例。

---

解析

---

---

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; 
}
//函数区