题解 | 收集纸片

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define all(a) a.begin(), a.end()
using vi = vector<int>;
using vpii = vector<pair<int, int>>;

void solve() {
    int n, m;cin >> n >> m;
    int x, y;cin >> x >> y;
    int len;cin >> len;
    vpii a(len);
    for (int i = 0;i < len;i++) {
        cin >> a[i].first>>a[i].second;
    }
    vi idx(len);
    for (int i = 0;i < len;i++) {
        idx[i] = i;
    }
    int mn = 1e9;
    do {
        int sum = 0;
        int x0 = x, y0 = y;
        for (int i : idx) {
            auto [xx, yy] = a[i];
            sum += abs(xx - x0) + abs(yy - y0);
            x0 = xx, y0 = yy;
        }
        sum += abs(x - x0) + abs(y - y0);
        mn = min(mn, sum);
    } while (next_permutation(all(idx)));
    cout << "The shortest path has length "<< mn << endl;
}

/*

*/

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t = 1;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        //cout << "----Test " << i << "----" << endl;
        solve();
    }
    return 0;
}

全排列枚举，全排列下标数组对每一种排列模拟路径，取最小值