题解 | 收集纸片

数据很小，可以考虑直接暴力枚举所有的状态，然后暴力的走

#include <bits/stdc++.h>
#define il inline

using namespace std;
using ll = long long;
using ull = unsigned long long;
using int128=__int128_t;

const ll N = 1e6 + 5, mod =998244353, inf = 2e18;
const double esp=1e-9;
double PI=3.1415926;

il void solve(){  
    int n,m,sx,sy;
    cin>>n>>m>>sx>>sy;
    int q;
    cin>>q;
    vector<pair<int,int>>pos(q);
    for(auto &[x,y]:pos){
        cin>>x>>y;
    }
    ll ans=inf;
    sort(pos.begin(),pos.end());
    do{
        ll cur=abs(sx-pos[0].first)+abs(sy-pos[0].second);
        auto [x,y]=pos[0];
        for(int i=1;i<q;i++){
            cur+=abs(x-pos[i].first)+abs(y-pos[i].second);
            x=pos[i].first;
            y=pos[i].second;
        }
        cur+=abs(sx-x)+abs(sy-y);
        ans=min(ans,cur);
    }while(next_permutation(pos.begin(),pos.end()));

    cout<<"The shortest path has length "<<ans<<'\n';
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int t = 1;

    cin >> t;

    while (t--) {

        solve();

    }

    return 0;
}