U23347.[模板]BFS最短路线

通过率：0%

时间限制：1.00s

内存限制：128MB

泛洪算法，以及获得路线练习。为了方便练习，数据保证路线的唯一性。

有一个字符矩阵，. 表示可以行走，# 表示障碍，无法行走。先要求从左上角 (1, 1) 走到右下角 (n, m) 的最短的步数，以及最短的一条行走路线。

模板题，因此数据保证唯一性

第一行两个整数 $n, m$ 表示 $n$ 行 $m$ 列

之后有 $n$ 行每行 $m$ 个字符输入.

第一行一个整数表示最少的步数。

第二行输出从 (1,1) 开始到达 (n,m) 的一条最短路线。每两个位置之间用一个空格隔开。

输入#1

7 10
......#...
...##...#.
.#......#.
.######.#.
.#......#.
.##.#.###.
....#.....

输出#1

17
(1,1) (1,2) (1,3) (1,4) (1,5) (1,6) (2,6) (2,7) (2,8) (1,8) (1,9) (1,10) (2,10) (3,10) (4,10) (5,10) (6,10) (7,10)

1 ≤ n,m ≤ 100