2652: T4-走迷宫
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：5
解决：3
题目描述
给定 n×m 个方格构成的图，每个格子都有一种地形：
有一些格子是墙，以符号 # 表示，墙不可通行。
有一些格子是空地，以符号 . 表示，空地可以通行。
请计算，从左上角的方格出发，最少需要移动多少步才能到达右下角的方格。在移动过程中，不能进入地形为墙的方格，保证起点与终点方格地形不是墙。且移动时，只能移动到水平或垂直方向相邻的方格。
有一些格子是墙，以符号 # 表示，墙不可通行。
有一些格子是空地，以符号 . 表示，空地可以通行。
请计算，从左上角的方格出发，最少需要移动多少步才能到达右下角的方格。在移动过程中，不能进入地形为墙的方格，保证起点与终点方格地形不是墙。且移动时，只能移动到水平或垂直方向相邻的方格。
输入
第一行：单个整数 n 与 m
第二行到第 n+1 行：第 i+1 行每行有 m 个整数表示第 i 行的地形
第二行到第 n+1 行：第 i+1 行每行有 m 个整数表示第 i 行的地形
输出
单个整数，表示起点到终点最短路径长度
若无解，输出 No solution
若无解，输出 No solution
样例输入 复制
4 5
.#...
.#.#.
.#.#.
...#.样例输出 复制
13提示
30% 的数据，1≤n,m≤4
60% 的数据，1≤n,m≤10
100% 的数据，1≤n,m≤1000
60% 的数据，1≤n,m≤10
100% 的数据，1≤n,m≤1000