题解 | 收集纸片

#include<bits/stdc++.h>
using namespace std;
const int N=25;
int mp[N][N];
int n;
int minlen=0x3f3f3f3f;
int res;
int x,y;
pair<int,int> pos;
pair<int,int> mb[N];
bool vis[N];

void dfs(int num)
{
	if(num==n)
	{
		res+=abs(x-pos.first)+abs(y-pos.second);
		minlen=min(minlen,res);
		res-=abs(x-pos.first)+abs(y-pos.second);
		return;
	}
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			pair<int,int> tmp=pos;
			vis[i]=true;
			res+=abs(mb[i].first-pos.first)+abs(mb[i].second-pos.second);
			pos=mb[i];
			dfs(num+1);
			pos=tmp;
			res-=abs(mb[i].first-pos.first)+abs(mb[i].second-pos.second);
			vis[i]=false;
		}
	}
	
}

int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		minlen=0x3f3f3f3f;
		res=0;
		int l,w;
		cin>>l>>w;

		cin>>x>>y;
		pos={x,y};
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>mb[i].first>>mb[i].second;
		}
		memset(vis,0,sizeof vis);
		dfs(0);
		cout<<"The shortest path has length "<<minlen<<endl;
	}
	
	return 0;
}