问题描述

具体描述见教材p193： 小A是个小术士，他很喜欢单挑BOSS。单挑BOSS是指在一个N x M的矩形(N,M<=100)，上面遍布了小怪和传送门，其中1表示有小怪，0表示无小怪，大写字母表示传送门，传送门是一对相同的大写字母， 如遇到一个大字A则马上可以到达另一个大写A的位置（次数不限，但每次进入传送点只传送过去， 不会再传送回来，数据保证每个传送门有且权有相对应的另一个传送门）。小A在左上方(1,1)出发，BOSS躲中右下方(N,M)。小A绝不会在小怪身上浪费时间（当然是绕开他们），并且想通过传送门尽快到达BOSS身边。

格式

输入

第1行两个整数N和M。 下面N行，每行M个数（入口点和BOSS点无小怪和传送门），表示地图。地图数据之间无空格。每步只能走一格，方向上下左右。左上角为入口点，右下角为出口点。

输出

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

样例

3 4
0000
00A0
A000

4

4 6 
010100
01A100
011101
0000A0

10

限制

1s, 64MB.