Collecting Packages

90 阅读 0 评论 60 点赞

我是靠谱客的博主忧伤皮带，最近开发中收集的这篇文章主要介绍Collecting Packages，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目连接: Collecting Packages

题目:

仓库里有一个机器人，他想收集n个包裹。仓库可以表示为一个坐标网格。最初，机器人停留在点（0,0）。第i个包在点上（x i，y i）。保证在同一点上没有两个包。还可以保证点（0,0）不包含包。
机器人是半断的，只能向上（‘U’）和向右（‘R’）移动。换句话说，在一次移动中，机器人可以从点（x，y）移动到点（x+1，y）或点（x，y+1）。
如上所述，机器人希望收集所有n个包（按任意顺序）。他想用最少的动作来完成。如果有几个可能的遍历，机器人想要选择字典上最小的路径。
长度n的字串S小于长度n的字符串t，如果有一些索引1＜j＜n，对于i i从1到j＝1的SI＝Ti和Sj＜Tj。它是字符串的标准比较，就像在字典中一样。大多数编程语言都是这样比较字符串的。

Input
输入的第一行包含一个整数t（1≤t≤100）-测试用例的数量。接下来是测试用例。
测试用例的第一行包含一个整数n（1≤n≤1000）-包的数量。
接下来的n行包含包的描述。第i个包被给出为两个整数Xi和Yi（0下限Xi，Yi±1000）-包的x坐标和包的y坐标。
保证在同一点上没有两个包。还可以保证点（0,0）不包含包。
测试中测试用例上所有值n的总和不超过1000。

Output
打印每个测试用例的答案。如果不可能从（0,0）开始以某种顺序收集所有n个包，请在第一行打印“NO”。否则，请在第一行打印"YES”。然后打印最短路径-由字符“R”和“U”组成的字符串。在所有这些路径中，选择字典上最小的路径。

Example
Input
3
5
1 3
1 2
3 3
5 5
4 3
2
1 0
0 1
1
4 3
Output
YES
RUUURRRRUU
NO
YES
RRRRUUU

解题思路:

本题可以理解为一个BFS题目, 由于要求打印U和R, 可以把每次的路径存储在字符串中, 最后输出字符串即可.

但本题实际上也是一个有规律的题目, 机器人拿物品一定是先拿最靠左下的, 可以理解为x和y最小的, 如果有一个物品a的x坐标比另外一个物品b的x坐标要大, 但是y坐标要小, 则机器人一定是拿不全物品的. 而从一个点到另一个点, 由于要求打印的顺序是按字典从小到大, 实际上就是要先打印R后打印U, 即: 先往右跑, 再往上跑, 实际上每个点打印的R和U就取决于他到下一个点的△x与△y

AC代码:

#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#define ll long long
using namespace std;
struct node {
int x, y;
}a[1005];
bool cmp(node a, node b) //排序规则
{
if (a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
int main(void)
{
int t; cin >> t;
while (t--) {
memset(a, 0, sizeof(a));
int dx = 0; int dy = 0;
int n; cin >> n;
for (int i = 0; i < n; i++) {
int x, y; cin >> x >> y;
a[i] = { x, y };
}
sort(a, a + n, cmp);
/* 判断是否是不可达情况 */
for (int i = 0; i < n - 1; i++) {
if (a[i].y > a[i + 1].y) { cout << "NO" << endl; goto here; }
}
/* 情况可达 */
printf("YESn");
for (int i = 0; i < n; i++) {
int cx = a[i].x - dx;
int cy = a[i].y - dy;
for (int j = 0; j < cx; j++) {
printf("%c", 'R');
}
for (int j = 0; j < cy; j++) {
printf("%c", 'U');
}
dx = a[i].x; dy = a[i].y;
}
printf("n");
here:;
}
return 0;
}