题目描述

给定 $n\times m$ 个方格构成的图，每个格子都有一种地形：

• 有一些格子是墙，以符号 # 表示，墙不可通行。
• 有一些格子是空地，以符号 . 表示，空地可以通行。

请计算，从左上角的方格出发，最少需要移动多少步才能到达右下角的方格。在移动过程中，不能进入地形为墙的方格，保证起点与终点方格地形不是墙。且移动时，只能移动到水平或垂直方向相邻的方格。

输入格式

• 第一行：单个整数 $n$ 与 $m$
• 第二行到第 $n+1$ 行：第 $i+1$ 行每行有 $m$ 个整数表示第 $i$ 行的地形

输出格式

• 单个整数，表示起点到终点最短路径长度
• 若无解，输出 No solution

4 5
.#...
.#.#.
.#.#.
...#.

13

3 3
..#
.#.
#..

No solution

数据范围

• $30\%$ 的数据，$1\leq n, m\leq 4$
• $60\%$ 的数据，$1\leq n, m\leq 10$
• $100\%$ 的数据，$1\leq n, m\leq 1000$