5730. 调箱师

单点时限: 1.0 sec

内存限制: 512 MB

小山最近玩起了推箱子游戏。推箱子游戏的规则是:

  1. 游戏目标:将所有的箱子推到指定的目标位置上,完成每个关卡。

  2. 游戏地图:游戏地图由方块组成的网格构成,有墙壁、空地、箱子和目标位置。

  3. 角色操作:通过控制一个角色在地图上移动,可使用键盘或触摸屏,角色可以向上、下、左、右四个方向移动,但不能穿过墙壁或箱子。

  4. 箱子推动:玩家可以推动地图上的箱子,但只能朝着箱子的空白一侧推动。如果箱子被墙壁或其他箱子挡住,就无法移动。

  5. 目标位置:地图上会标记出目标位置,玩家需要将所有的箱子都推到这些位置上才能完成关卡。

  6. 通关条件:当所有的箱子都被推到目标位置上时,玩家即可通关。

现在游戏地图里只有一个角色,一个箱子,和一个目标位置,并且保证位置不重合。小山想知道能否通关

输入格式

第一行,一个正整数$T$,表示$T$组数据。

对于每组数据,第一行两个整数$n,m(1\leq n,m \leq 500)$表示地图的行数和列数。

接下来$n$行,每行$m$个字符。表示地图。

  • .表示空地
  • #表示墙壁
  • O表示箱子
  • X表示目标位置
  • S表示角色

数据保证所有数据均满足:$\sum n\times m \leq 10^6$

输出格式

对于每组数据,输出一行YesNo,表示是否能通关。

样例

Input
2
10 10
####.....#
#..O.###.#
#....###..
#.#######.
#.#X...##.
#.###..##.
..###.###S
......####
####..####
##########
10 10
###......#
#..O.###.#
#....###..
#.#######.
#.#X...##.
#.###..##.
..###.###S
......####
####..####
##########
Output
No
Yes

2 人解决,11 人已尝试。

2 份提交通过,共有 26 份提交。

9.7 EMB 奖励。

创建: 4 月,3 周前.

修改: 4 月,3 周前.

最后提交: 2 月,1 周前.

来源: N/A

题目标签