首页 > 试题广场 >

小红的路径

[编程题]小红的路径
  • 热度指数：1 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}给定一个 2 行 n 列的矩阵，行编号为 1, 2，列编号为 1, 2, \dots, n。我们使用 (i,j) 表示矩阵中从上往下数第 i 行和从左往右数第 j 列的格子。
\hspace{15pt}你初始位于 (x_1, y_1)，目标位置是 (x_2, y_2)。你需要找到一条从初始位置出发，到达目标位置的路径，满足：
\hspace{23pt}\bullet\,路径经过矩阵中的每一个格子恰好一次；
\hspace{23pt}\bullet\,每一步只能向上下左右四个相邻格子移动。

输入描述:
\hspace{15pt}在一行上输入五个整数 n, x_1, y_1, x_2, y_2\left( 1\leqq n \leqq 2\times 10^5;\, 1 \leqq x_1, x_2 \leqq 2;\, 1 \leqq y_1, y_2 \leqq n\right)。
\hspace{15pt}特殊的，保证 (x_1, y_1) \neq (x_2, y_2)。


输出描述:
\hspace{15pt}如果不存在符合条件的路径，请输出 -1；否则，输出一个长度为 2 \times n-1，仅由字符 \texttt{U}、\texttt{D}、\texttt{L}、\texttt{R} 组成的字符串，表示符合条件的路径。四个字符分别表示向上、向下、向左、向右移动一格。

\hspace{15pt}如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。
示例1

输入

4 1 2 2 4

输出

LDRRURD

说明

\hspace{15pt}在这个样例中，输出描述的移动路径如下图所示：

示例2

输入

2 1 2 2 1

输出

-1

说明

\hspace{15pt}在这个样例中，矩阵如下图所示。


备注:
\hspace{15pt}在几乎全部的情况下，PyPy 的运行速度优于 Python，我们建议您选择对应版本的 PyPy 进行提交、而不是 Python。
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

难度：
0条回答 29浏览

热门推荐

相关试题

小红的路径

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号