数据结构与算法专题题库

1013. 迷宫搜索

单点时限: 2.0 sec

内存限制: 512 MB

给定一个迷宫,其中$s$表示入口,$t$表示出口,保证迷宫只有一个入口和出口。
#表示障碍物,.表示可以通过。
两个格子相邻当且仅当两个格子有公共的边(4联通模型)。
求从$s$到$t$的最短路径长度。

输入格式

第一行两个数$n,m$表示迷宫的大小。
接下来$n$行,每行$m$个字符。
满足$n \times m \leq 10^5$

输出格式

一个数表示最短距离,如果不连通则输出-1

样例

Input
4 3
s.#
...
.#t
...
Output
4

提示

$n \times m \leq 10^5$如何分配内存?

不限期开放

题目列表