某 和小 正在玩一个推箱子游戏。游戏是这样的,小 给出一个 的方阵,方阵中有的格子是墙,有的格子是空地,还有的格子是箱子或者目标点。某 的目标是,通过推动箱子的方式,使得每个箱子都能够到达一个目标点。
由于整个游戏都是在纸上进行的,为了减轻小 的负担,游戏可能和正常的推箱子略有不同。
某 将操控位于 的小人(这个点一定是空地或者目标点),完成这个目标。小人只能向上下左右四个方向移动。
空地和目标点是可以自由通行的,而墙是永远无法通行的。如果人物位于箱子旁边的格子,向箱子方向前进一步,此时当且仅当该箱子及其箱子背后在人物运动方向所在的射线上的箱子没有被墙挡住时,这些箱子均会往人物运动方向运动一格,反之箱子和人均不会移动。
比如这样的情况( 代表箱子, 代表空地, 代表墙):
xxxxxxxxxx
######
#.*.##
#B**.#
#.A..#
######
人物在 处时,无法向上移动,因为上面的 个箱子被墙挡住了。
人物在 处时,如果向右移动,那么地图将变成这个样子:
xxxxxxxxxx
######
#.*.##
#.B**#
#.A..#
######
你需要帮助某 ,输出一个方案,使得他能够完成他的目标。
第一行两个数 ,表示方阵的大小。
第二行两个数 ,表示人物初始位置。
后 行每行 个字符,其中:
字符 表示墙,字符 表示空地,字符 表示箱子,字符 表示目标点。
一行字符串表示你的答案。人物向上下左右移动分别对应着 字符。虽然本题对解的长度不做要求,但是你的解必须不大于 个字符。
xxxxxxxxxx
7 9
4 5
#########
####+####
####*####
#+.*.*+##
###*#####
###+#####
#########
xxxxxxxxxx
AADSWDDAW
这是一道提交答案题。
你需要将你的答案文件分别命名为 至 ,压缩成一个 压缩包来提交。
具体数据范围详见下发的输入数据。