收集金币（人人网笔试）

朴灿烈づ我的快乐病毒、 2022-06-07 07:50 194阅读 0赞

题目描述：

小M来到了一个迷宫中，这个迷宫可以用一个N\*M的矩阵表示。在这个迷宫的某些位置中存在金币。一开始小M在迷宫的入口：矩阵的左上角，位置(1，1)处；迷宫的出口位于矩阵的右下角，位置(N,M)处。每一次小M可以选择向下或者向右走到一个相邻的格子，但是不能跨出迷宫外。现在小M想收集完迷宫中的所有金币并最后到达迷宫的出口，请你帮她规划一条最短的路径。

输入

第一行包含三个整数N,M,K，表示矩阵的规模以及金币的数目。

2≤N,M≤100，0≤K≤1000

接下来K行每行包含两个整数Xi,Yi，表示第i个金币的位置，位于从上往下第Xi行，从左往右第Yi列。

1≤Xi≤N,1≤Yi≤M

输出

若不存在满足条件的路径，输出Impossible。

若最短路径存在，则输出小M移动的序列：

‘R’：表示向右；

'D’：表示向下。

若存在多个答案，你需要输出字典序最小的答案。

样例输入

3 3 2

1 2

3 3

样例输出

RDDR

**思路**：首先将金币按坐标进行排序，怎么排序呢？排序规则是首先按横坐标X从小到大排序，然后如果两个点的横坐标X相等，则按照纵坐标Y从小到大进行排序，排完以后从起始位置依次到达这些金币的位置，就一定是一条最短的路径。由于本题只能向下或向右走，故在依次收集金币的时候需要判断当前坐标X和Y是否都不小于前一个金币位置的X和Y，如果是，则满足继续收集，否则，不满足退出，即不存在一条满足条件的最短路径。

如下图所示：A(1,2)、B(2,2)、C(1,3)、D(3,3)为金币所在位置，排序以后为A(1,2)、C(1,3)、B(2,2)、D(3,3)。从(1,1)位置开始，依次收集金币，当收集完金币C是，此时小M位于(1,3)的位置，由于只能向下或向右移动，故小M无法到达金币B的位置，因此不存在这样一条路径。同理先去收集金币B，也同样无法收集金币C。如果去掉金币C，则就可以依次收集金币ABD。移动的路径为RDDR。

![Image 1][]

代码实现如下：

#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <string>
    using namespace std;
    
    struct node
    {
        int x;
        int y;
    };
    
    //自定义排序比较规则
    bool Compare(node n1, node n2) {
        if (n1.x != n2.x)
            return n1.x<n2.x;
        return n1.y < n2.y;
    }
    
    int main()
    {
        int N, M, K;
        cin >> N >> M >> K;
        vector<node> arr(K);
        for (int i = 0; i < K; i++) {
            cin >> arr[i].x >> arr[i].y;
        }
        sort(arr.begin(), arr.end(), Compare);
    
        bool flag = true;    //标记是否存在最短路径
        string str;
    
        for (int i = 0; i < K; i++) {
            //从起始位置到第一个金币位置
            if (i == 0)
            {
                for (int j = 0; j < arr[i].x - 1; j++)
                    str += "D";
                for (int j = 0; j < arr[i].y - 1; j++)
                    str += "R";
            }
            else {
                if (arr[i].x >= arr[i - 1].x && arr[i].y >= arr[i - 1].y)
                {
                    for (int j = 0; j < arr[i].x - arr[i - 1].x; j++)
                        str += "D";        //向下移动
                    for (int j = 0; j < arr[i].y - arr[i - 1].y; j++)
                        str += "R";        //向右移动
                }
                else {
                    flag = false;          //此时就出现了类似于金币B和C的情况
                    break;
                }
            }
        }
    
        if (flag) {
            //最后需要到达出口位置
            for (int j = 0; j < N-arr[K-1].x; j++)
                str += "D";
            for (int j = 0; j < M-arr[K-1].y; j++)
                str += "R";
            cout << str << endl;
        }
        else
            cout << "Impossible" << endl;
        return 0;
    }

[Image 1]: