练习专区

今天的一小步就是明天的一大步
Problem 1890 唯一的错过
Accepted: 2   Total Submit: 4
Time Limit: 1000ms   Memory Limit: 30720KB
Description

迷宫建成m*n的矩形方格,左上角的坐标是(00)右下角的坐标是(m-1n-1),规定起点在左上角,终点在右下角,从起点到终点可能有多条路径,只能向右或向下走。现在有2个人从起点出发,到达终点,要求他们的路径不能有重复,已知该走法唯一(即起点到终点只有2条不重复的路),请找出他们要怎么走才能错过?并按要求输出他们走过的路径。

Input
输入有若干个案例,每个案例的第1行有两个整数m、n,分别表示迷宫的行数和列数,接着有m行n列的数据,起点用S表示,终点用E表示,其余为0或1,1表示墙即不能走。m=n=0表示结束。
Output
按样例输出每个人向右或是向下走过的路径序列,右用R表示,下用D表示,先输出第一步向下走的人的路径,其次是另一个人,两路径用空格隔开。
Sample Input
4 5
S0100
00011
01000
0000E
5 4
S000
0010
1010
1000
110E
7 8
S0100000
00000010
00000000
11110110
11110000
11111100
0001010E
4 5
S0000
01110
01110
0000E
0 0
Sample Output
DDDRRRR RDRDRRD
DRDDRDR RRRDDDD
DDRRRRDDRRDDR RDRRRRDRRDDDD
DDDRRRR RRRRDDD
Hint
提交     返回