logo AlgoBeat OnlineJudge
登录 注册

#999. 『ZOI Round #1』俄罗斯方块

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: AlgoBeat 官方账号

题目描述

小 Z 最喜欢玩俄罗斯方块啦。最近他发明了一种俄罗斯方块的新玩法:将红色方块移到蓝色区域。

在这种新玩法中,俄罗斯方块可以向上下左右四个方向移动,但是不可以旋转。为了增加游戏的难度,游戏中增设了墙。在方块的移动过程中,不能穿过墙或与墙重叠。除了墙以外的区域都是空地,方块可以任意移动。

游戏区域可以用一个 的矩阵表示,其中字符 表示第 行第 列的方格。其中,. 表示空地,# 表示墙,A 表示红色方块的初始位置,B 表示移动目标蓝色区域。

小 Z 想知道他是否可以将红色方块移到蓝色区域。若可以,他想知道至少需要移动多少次。

输入格式

第一行包含两个正整数 ,表示游戏区域的长和宽。

接下来 行,每行 个字符,即矩阵 ,表示游戏区域的内容。

输出格式

第一行包含一个字符串 YesNo,表示是否可以将红色方块移到蓝色区域。

第二行包含一个整数,表示至少需要移动多少次。若无法将红色方块移到蓝色区域,输出 -1

样例

输入 #1

4 6
.A.#..
AAA#..
....B#
#..BBB

输出 #1

Yes
5

输入 #2

4 6
.A.#..
AAA#..
....B#
##.BBB

输出 #2

No
-1

数据范围与提示

样例解释

在样例 1 中,游戏区域如下图所示。其中,白色表示空地,黑色表示墙。

最少次数的移动方案为下,右,下,右,右。

数据范围

本题采用捆绑测试

  • Subtask 1(20 points):
  • Subtask 2(20 points):
  • Subtask 3(10 points):
  • Subtask 4(50 points):无特殊限制。

对于所有测试数据,A 部分和 B 部分存在且连通且形状和方向完全相同。