题解 | 收集纸片DFS做法

dfs（捡起的纸片数量，当前所在位置）

#include<bits/stdc++.h>
using namespace std;

int n, ans = 1e9;

struct pos
{
	int x;
	int y;
} paper[20];

bool book[30];

int cnt = 0;

void dfs(int step, int p)
{
	if (step == n)
	{
		cnt += abs(paper[0].x - paper[p].x) + abs(paper[0].y - paper[p].y);
		ans = min(cnt, ans);
		return ;
	}
	for (int i = 1; i <= n; i++)
	{
		if (!book[i])
		{
			book[i] = 1;
			int tmp = cnt;

			cnt += abs(paper[i].x - paper[p].x) + abs(paper[i].y - paper[p].y);
			dfs(step + 1, i);

			cnt = tmp;
			book[i] = 0;
		}
	}

}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int dd, d;
	int x0, y0;
	int tt;
	cin >> tt;
	while (tt--)
	{
		cin >> dd >> d >> x0 >> y0;
		paper[0].x = x0, paper[0].y = y0;
		cin >> n;
		ans = 1e9;
		cnt = 0;
		memset(book, 0, sizeof(book));
		for (int i = 1; i <= n; i++)
			cin >> paper[i].x >> paper[i].y;
		dfs(0, 0);
		cout << "The shortest path has length " << ans << "\n";

	}
	return 0;
}