You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目内容

小红有一些宝物藏在了家里的地板下面，地板为一个一个方格。现在他忘了有多少宝物,也忘了存放的位置。他现在希望你从一个点出发，翻开所有的地板一次且仅有一次。现在想让你找出翻开的路径。

输入描述

两个正整数 $n$ 和 $m$ ，用空格隔开表示家中地板的大小

$1 \leq n,m \leq 1000$

保证 $n$ ， $m$ 不同时为 $1$

第一行输入两个正整数 $x$ 和 $y$ ，代表初始的点为第 $x$ 行第 $y$ 列

第二行输入一个长度为 $n*m-1$ 的字符串，共有 $4$ 种字符；

" $W$ "向上走

" $S$ "向下走

" $A$ "向左走

" $D$ "向右走

有多解时输出任意即可。

输入

3 3

输出

3 1
DWAWDDSS

说明

如以下顺序所示

`5`	`4`	`3`
`6`	`7`	`2`
`9`	`8`	`1`

考虑起点为 $(1,1)$ ，其实可以构建一个固定的路径

如果当前在偶数行，就往左走，如果在奇数行，就往右走（因为起始点为奇数行）

然后走到每一行的末尾，需要往下走一格，整个路径就形成一个蛇字形。