题解 | 收集纸片

#include <bits/stdc++.h>
#include <unordered_set>

//#define int long long
using ll = long long;
using namespace std;

int dx[] = { 0,0,1,-1,1,1,-1,-1 };
int dy[] = { 1,-1,0,0,1,-1,1,-1 };
int days[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
const int mod = 1e9 + 7;
const int MOD = 998244353;

template<typename T>
struct cmp /*cmp<T>()*/
{
    bool operator()(const T& a, const T& b)
    {
        if(a.first != b.first)
            return a.first<b.first;
        else
            return a.second<b.second;
    }
};

//////////////////////////////////////////////////////////
void solve()
{
    int n,m;
    cin>>n>>m;
    int x,y;
    cin>>x>>y;
    int k;
    cin>>k;
    vector<pair<int,int>> v(k);
    for(int i=0;i<k;i++)
        cin>>v[i].first>>v[i].second;
    
    sort(v.begin(),v.end(),cmp<pair<int,int>>());
    int ans=INT_MAX;
    do 
    {
        int dis=0;
        int tx=x;
        int ty=y;
        for(auto [hx,hy] : v)
        {
            dis+=abs(hx-tx)+abs(hy-ty);
            tx=hx;
            ty=hy;
        }
        dis+=abs(x-tx)+abs(y-ty);
        ans=min(ans,dis);
    }while (next_permutation(v.begin(),v.end()));
    cout<<"The shortest path has length "<< ans <<endl;
}

//////////////////////////////////////////////////////////

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    //cout << fixed << setprecision(5);
    while (T--) {
        solve();
    }
    return 0;
}