提取宝石问题

题目

宝石采集问题

假设有这样一个场景，一个宽敞的房间内分布着n颗宝石，每颗宝石的位置均可通过坐标(x, y)进行标识。现要求从某一特定位置出发，依次访问所有宝石所在的位置并将其取走，最终返回初始出发点。试求解在这一过程中所需行走的最短路径长度。
本题中允许采用直线路径进行移动。

思路

在该情境下，采用列举的方式进行分析，由于不同路径的顺序将影响最终的行进距离，因此需要列举所有经过1至n这n个位置的排列方式。
对n个位置顺序的列举本质上属于排列组合问题，因此可以借助C++语言中提供的next_permutation函数来高效获取下一个排列，该操作的时间复杂度为O(n)。

细节
初始点与终点是确定不变的，因此数组中的首个元素和末尾元素不参与排列过程。

代码

    #include <bits/stdc++.h>
    #define N 15
    using namespace std;
    int n = 4; // 4个宝石
    int id[N] = {0, 1, 2, 3, 4, 0};
    double x[N] = {0, 2, 2, 3, 5, 0}; // 宝石的x坐标
    double y[N] = {0, 1, 4, 5, 6, 0}; // 宝石的y坐标