4405 - 走迷宫 Ⅳ

迷宫是一个N \times M ,N行M列的矩阵。玩家需要从初始位置(2,2)移动到终点位置(n-1,m-1),移动到相邻(上/下/左/右)的格子视为1步,求最小移动步数。

'.'表示是一个空格,迷宫可以站人

'*'表示是迷宫的墙/障碍物,不能经过,停留

输入

第一行两个数字N,M

下面N行,每行M个字符,描述迷宫每格的状态

输出

输出第一行为一个数字,为最小步数。如果无法到达,则只输出-1

如果可以到达,则输出所有依次停留的网格坐标(包括起点和终点) ,可以输出任意满足题意的解

样例

输入

7 8
********
*..*.***
**.*..**
*......*
**...*.*
**.**..*
********

输出

10
2 2
2 3
3 3
4 3
4 4
4 5
4 6
4 7
5 7
6 7

提示

N,M \leq 500 保证迷宫的最外围都是墙

来源

原创

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题