问题 4839 --4.魔兽世界

4839: 4.魔兽世界

题目描述

  小明来到厄运之槌开始单刷,厄运之槌的地图是一个 $N \times M $ 的矩形,上面遍布了小怪和传送门,其中 $1$ 表示有小怪, $0$  表示无小怪,大写字母表示传送门;
传送门:例如,走到  $A$  传送门点将传送到另一个  $A$  传送门点(次数无限,但每次进入传送点只传送过去,不会在传送回来);
数据保证每个传送门有且仅有相对应的另一个传送门。

入口 0 0 0
0 0 A 0
A 0 0 BOSS



而入口在左上方  $(1,1)$ ,BOSS却躲在右下方  $(N,M)$ 
小明非常急切的想要完成单刷,所以,小明绝不会在小怪身上浪费时间(当然是绕开他们),并且想通过传送门尽快到达 BOSS 身边。
现在小明找到了你,请求你帮助他。

输入

第一行两个数  $n,m$ 
下面  $n$ 行,每行  $m$  个数(入口点和BOSS点无怪和传送门),表示厄运之槌的地图。
地图数据之间无空格。每步只能走一格,方向上下左右。
左上角为入口点,右下角为出口点。

输出

一个整数,表示小明最少需要走多少步。
如果小明不能走到目标,则输出 “No Solution.”。

样例输入输出

输入#1 复制
3 4
0000
00A0
A000
输出#1 复制
4

提示

样例解释
路线如图:

对于 $60\%$ 的数据,$ 1 \leq n,m \leq 20$;
对于 $100\%$ 的数据,$ 1 \leq n,m \leq 100$。

序号 标题 作者 发表时间 费用 订购数 操作