小红的模拟题

题号：NC294403
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
Special Judge, 64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 给定一个 $n$ 行 $m$ 列的网格，我们使用 $(i,j)$ 表示网格中从上往下数第 $i$ 行和从左往右数第 $j$ 列的格子。小红现在位于 $(1,1)$ ，准备前往 $(n,m)$ 。
$\hspace{15pt}$ 然而，不是所有的格子都是可以通行的，有且恰有一个格子是陷阱格，一旦小红踏入陷阱格，就会直接去逝。保证这个陷阱格不会出现在 $(1,1)$ 和 $(n,m)$ 。
$\hspace{15pt}$ 小红每一步只能向右或者向下前进。请你帮小红规划一条行动路线，使得她可以顺利到达 $(n,m)$ 。

$\hspace{15pt}$ 行动路线为一个仅由字符 $\texttt{`D'}$ 、 $\texttt{`S'}$ 构成的字符串 $s$ ，第 $i$ 个字符代表小红第 $i$ 次行动的方向。记第 $i$ 次行动前小红位于 $(x,y)$ ，则：
$\hspace{23pt}\bullet\,$ 若 $s_i = \texttt{`D'}$ ，则小红向右移动一格即抵达 $(x,y+1)$ ；
$\hspace{23pt}\bullet\,$ 若 $s_i = \texttt{`S'}$ ，则小红向下移动一格即抵达 $(x+1,y)$ 。

输入描述:

第一行输入两个正整数 ，代表网格的行数和列数。 
接下来的  行，第  行输入一个长度为  的、仅由  和  构成的字符串 。其中  表示格子  可以通行， 表示格子  是陷阱格。

除此之外，保证有且只有一个陷阱格，且不位于  和 。

输出描述:

输出一个字符串，代表小红的行动路线。
如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

示例1

输入

复制

2 3
...
.#.

输出

复制

DDS

说明

在这个样例中，小红先向右走两步，然后向下走一步，即可安全到达目的地。