收集金币（人人网笔试）

思路：首先将金币按坐标进行排序，怎么排序呢？排序规则是首先按横坐标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。

代码实现如下：

#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;
}