← 返回题目列表

AtCoder · abc453_d

D. 直走

中文机器翻译题面 查看原题

分数: 425 点

问题陈述

有一个网格 H 行 \times W 列,高桥在该网格中上下左右移动。
单元格的状态 i从顶部算起的第行和 j左起第 列 (1\leq i\leq H, 1\leq j\leq W) 由字符表示 S_{i,j}.
S_{i,j} 是其中之一 #, ., o, x, S, G.

  • If S_{i,j}=#:无法输入此单元格。
  • If S_{i,j}=.:该单元格可以自由进入和退出。也就是说,进入这个单元格后,高桥可以向上、下、左、右方向移动到任何相邻的单元格(如果存在)。
  • If S_{i,j}=o:在这个单元格中, 高桥的移动方向必须与前一移动的方向相同。也就是说,进入这个牢房后,必须不改变方向移动到下一个牢房。
  • If S_{i,j}=x:在这个单元格中, 高桥不能沿与前一移动相同的方向移动。也就是说,进入这个牢房后,他必须改变方向才能移动到下一个牢房。车削 返回到前一个单元格的 180 度被视为改变方向。
  • If S_{i,j}=S:该单元格是高桥的起始位置。该牢房可以自由进出。
  • If S_{i,j}=G:这个单元格是高桥的目的地。该牢房可以自由进出。

正好有一个 (i,j) 与 1\leq i\leq H, 1\leq j\leq W 满意 S_{i,j}=S,正是一个令人满意的 S_{i,j}=G.

Takahashi 想要通过从起始位置向上、向下、向左或向右重复移动到相邻单元格来到达目的地。
判断这是否可能,如果可以,则输出最多一个有效的走法序列 5\times 10^6 在相邻单元格之间移动。
可以证明,如果在问题条件下存在有效的移动序列,则存在最多一个 5\times 10^6 移动。
只要移动次数最多为 5\times 10^6,没有必要最小化移动次数。

约束

  • 1 \leq H,W\leq 1000
  • S_{i,j} 是其中之一 #, ., o, x, S, G.
  • 正好有一个 (i,j) 满意 S_{i,j}=S 正是一个令人满意的 S_{i,j}=G.
  • H 和 W 是整数。

输入

输入由标准输入按以下格式给出:

H W
S_{1,1} S_{1,2} \ldots S_{1,W}
S_{2,1} S_{2,2} \ldots S_{2,W}
\vdots
S_{H,1} S_{H,2} \ldots S_{H,W}

输出

如果在满足条件的情况下无法到达目的地,则输出 第一行是 No ,第二行什么也没有。
如果在满足条件的情况下能够到达目的地,则输出 Yes 在第一行。
第二行,输出一个字符串 T 代表一系列动作。 T 必须满足以下所有条件。

  • 长度 \lvert T\rvert of T 介于 1 和 5\times 10^6,包括在内。
  • 每个字符 T 是其中之一 U, D, L, R.
    • 的 i- 第一个字符 T 正在 U, D, L, R 意味着在 i离开后第次移动,高桥分别移动到上方、下方、左侧或右侧的相邻单元格。
  • 对于 1\leq i\leq \lvert T\rvert,高桥不在格子外 i第一步。
  • 在移动过程中,不会违反每个单元格的条件。
  • 之后 \lvert T\rvert第一步,高桥位于目标单元格。只要满足这个条件,他就可以在到达目的地之前穿过目的地小区。 \lvert T\rvert第一步。

示例输入 1

3 5
.#...
.Sooo
..x.G

示例输出 1

Yes
DRUUDDRR

让细胞 (i,j) 表示位于 i从顶部算起的第行和 j左起第 列。
在示例输出之后,路径为:cell (2,2) \to 细胞 (3,2) \to 细胞 (3,3) \to 细胞 (2,3) \to 细胞 (1,3) \to 细胞 (2,3) \to 细胞 (3,3) \to 细胞 (3,4) \to 细胞 (3,5),到达目的地。
其他解决方案,例如 DRUURLRRDD 也被接受。 另一方面,由于高桥不能直接穿过牢房 (3,3),解决方案例如 DRRR 不被接受。


示例输入 2

3 3
#So
xoG
..#

示例输出 2

Yes
DDLURR

示例输入 3

2 2
So
oG

示例输出 3

No

满足条件时不可能到达目的地。