单点时限: 2.0 sec
内存限制: 512 MB
给定一个迷宫,其中$s$表示入口,$t$表示出口,保证迷宫只有一个入口和出口。
#
表示障碍物,.
表示可以通过。
两个格子相邻当且仅当两个格子有公共的边(4联通模型)。
求从$s$到$t$的最短路径长度。
第一行两个数$n,m$表示迷宫的大小。
接下来$n$行,每行$m$个字符。
满足$n \times m \leq 10^5$
一个数表示最短距离,如果不连通则输出-1
。
4 3 s.# ... .#t ...
4
$n \times m \leq 10^5$如何分配内存?