D.故宫元宵寻宝

D.故宫元宵寻宝

元宵节这一天，故宫举办了一个盛大的宴会。而在宴会之后，举办方还主持了一个寻宝活动。
故宫是由很多殿堂组成的，比如太和殿、中和殿、保和殿等等，并且故宫整体形状大致是一个正方形。我们把故宫抽象成一个
10×10 的方格地图，每个方格代表一个殿堂。从一个殿堂可以走到和它上下左右相邻的殿堂之一，并且要花费一分钟的时间。
现在举办方在其中 10 个殿堂中每个殿堂放了宝藏，玩家需要获得所有宝藏并且到达故宫出口，耗时最小者将获得大奖。具体的，玩家初始的时候在故宫的入口——左上角的殿堂（坐标为 (1,1)），玩家走到某个有宝藏的殿堂以后可以立即获得该宝藏，获取到所有宝藏后还需要走到出口——故宫的左下角（坐标为 (10,1)）。10 个宝藏的坐标分别为 (5,3), (5,10), (2,7), (4,5), (6,8)(7,7), (4,3), (10,10), (9,2), (3,4)。

题解：我们可以直接用 dfs 搜索下一次去取哪个宝藏。由于地图上没有障碍，两个点之间的最短就是 X 方向的坐标差加上 Y 方向的坐标差。
answer：41

/*
10
5 3
5 10
2 7
4 5
6 8
7 7
4 3
10 10
9 2
3 4
*/
#include <iostream>
#include <cmath>
using namespace std;
int x[11], y[11];
int ans = 1e9;
bool vis[11];
int n;
void dfs(int id, int step, int cost)
{if (step == n){ans = min(ans, cost + abs(x[id] - 10) + abs(y[id] - 1));return;}if (cost >= ans){return;}vis[id] = 1;for (int i = 1; i <= n; i++){if (!vis[i]){dfs(i, step + 1, cost + abs(x[id] - x[i]) + abs(y[id] - y[i]));}}vis[id] = 0;
}int main()
{cin >> n;x[0] = y[0] = 1;for (int i = 1; i <= n; i++){cin >> x[i] >> y[i];}dfs(0, 0, 0);cout << ans << endl;return 0;
}