P. 传火之路

Type: Default

1000ms

256MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

世界将要陷入无尽黑暗，身为不死人的你需要将那些不愿意传火的薪王干掉。在路上会遇到许多困难，你需要找一条最快的路来到薪王的所在地。

1.'S'表示起点
2.'#'表示墙壁
3.'.'表示可以通过的路
4.'@'表示篝火（篝火之间可以相互传送，且篝火数量不为 1 ）
5.'P'表示薪王房间
不死人能在一格地点上可能存在的四个相邻的格子移动，花费 1 个单位时间。篝火之间的传送不花费时间。
PS：传送不一定利于赶路

第 1 行：一个 N × M的地图（3<=N<=200,3<=M<=200）
第 2 行到第 N+1 行：每行 M 个字符，它们表示网格图中的一排。字符之间没有空格。

输出最快的路线需要的时间
如果到不了输出 -1

4 4
S.@.
.#..
..##
@P##

4 4
#S#.
.#..
....
...P

-1

1s, 1024KiB for each test case.