因为最多只有10个纸片,所以直接用stl的next_permutation函数暴力枚举全排列。
也就是拿纸片的先后顺序,然后每次排列计算求和 更新最小值即可。

#include<bits/stdc++.h>
using namespace std;
int a[15];
pair<int,int> q[15];
int main(){
    int t;cin>>t;
    while(t--){
        int nn,mm;cin>>nn>>mm;
        int ex,ey;cin>>ex>>ey;
        int n;cin>>n;
        for(int i=1;i<=n;i++) {
            int x,y;cin>>x>>y;
            q[i]={x,y};
        }
        for(int i=1;i<=n;i++) a[i]=i;
        int ans=1e9;
        do{
            int sum=abs(q[a[1]].first-ex)+abs(q[a[1]].second-ey)
            for(int i=2;i<=n;i++){
                sum+=abs(q[a[i]].first-q[a[i-1]].first)+abs(q[a[i]].second-q[a[i-1]].second);
            }
            sum+=abs(q[a[n]].first-ex)+abs(q[a[n]].second-ey);
            ans=min(ans,sum);

        }while(next_permutation(a+1,a+1+n));
        cout<<"The shortest path has length "<<ans<<endl;
    }
    return 0;
}