P14062

走迷宫 Ⅳ

难度 4 级小学算法入门 BFS DFS

讨论统计 40通过 114提交 35.1%通过率旧版界面

时间限制 1 秒 内存限制 128 MB

题目描述

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

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

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

第一行两个数字 $N，M$

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

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

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

样例 1

输入

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

输出

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

上一题下一题