问题 F: 上海市2023年12月月赛-丙组-T4-迷宫

问题 F: 上海市2023年12月月赛-丙组-T4-迷宫

时间限制: 1 Sec  内存限制: 128 MB
提交: 17  解决: 10
[提交] [状态] [讨论版] [命题人:]

题目描述

给定n x m个方格构成的图，每个格子都有一种地形:
有一些格子是墙，以符号#表示，墙不可通行。
有一些格子是空地，以符号.表示，空地可以通行。
请计算，从左上角的方格出发，最少需要移动多少步才能到达右下角的方格。在移动过程中，不能进入地形为墙的方格，保证起点与终点方格地形不是墙。且移动时，只能移动到水平或垂直方向相邻的方格。

输入

第一行:单个整数n与m
第二行到第n＋1行:第i＋1行每行有m个整数表示第i行的地形
1<=n, m<=1000

输出

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

样例输入 Copy 

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

样例输出 Copy 

13

提示

样例2：
3 3
..#
.#.
#..
输出：No solution
[提交][状态]