文件读写

• 输入文件home.in
• 输出文件home.out

限制

• 1000ms
• 512MB

题目描述

徐老师上夜班终于结束了！看着路边的灯光，回家这个词是如此的吸引人。

为了能够快速回家，徐老师用夺命连环call找到了大法师，希望大法师能帮他快点到家。

现在假设城市是一个 $N * M$ 的地图，徐老师公司在左上角$(1,1)$,徐老师家在右下角$(N,M)$，城市中存在一些建筑物，用 $'1'$ 表示，而能够行走的空地则用 $'0'$ 表示，徐老师只能在空地上移动，且只能上下左右移动，每次移动花费 $1$ 单位的时间

大法师为了帮助徐老师速回家，在地图上设置了一些传送法阵，但是因为是临时设接到电话需要布置法阵，所以法师也没有仔细观察地图，就在地图上随机布置了一些法阵。

法阵用大写字母表示，当 徐老师进入 $'A'$ 传送法阵时，可以传送到另一个 $'A'$ 传送法阵（一个法阵可以使用无限次）

如果有以下地图

00A
000
A00

当徐老师入坐标为 $(3,1)$ 的传送法阵时，会直接传送到坐标 $(1,3)$

注意这个传送不可控，即只要进入传送法阵必须要被传送到另一边

而如果需要从坐标为 $(1,3)$ 的传送法阵再次传送回来，则需要先移动到 $(2,3)$，再回到 $(1,3)$，重新进入法阵，才可以传送回 $(3,1)$

现在 徐老师想知道，他最快需要花费多少个单位的时间才能回到家？

若 徐老师不能回到家，则输出 "No Solution."（双引号不需要输出）

输入格式

输入第一行包含两个正整数 $N,M$ 表示有一个 $N * M$ 的地图

接下来 $N$ 行，每行 $M$ 个字符，题目保证输入只包含 $1,0$ 和大写字母，并且保证同一个大写字母有且只会出现两次

输出格式

输出只有一行，该行只有一个正整数，表示徐老师小需要花费的时间，若无法回家则输出 "No Solution."（双引号不需要输出）

数据范围

对于 $60\%$ 的数据，$N,M \leq 20$

对于 $100\%$ 的数据，$N,M \leq 100$

3 4
0000
0000
A0A0

3