元宵节这一天，故宫举办了一个盛大的宴会 。而在宴会之后，举办方还主持了一个寻宝活动 。
故宫是由很多殿堂组成的，比如太和殿、中和殿、保和殿等等，并且故宫整体形状大致是一个正方形 。我们把故宫抽象成一个
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 方向的坐标差 。
：41
【D.故宫元宵寻宝】
/*105 35 102 74 56 87 74 310 109 23 4*/#include #include 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;}