分数: 6 点
问题陈述
给你一个矩形网格 H 水平行和 W 垂直列。 广场位于 i从顶部开始的第行和 j从左边算起的第列称为 Sqaure (i, j).
每个方格要么是“没有墙的方格”,要么是“有墙的方格”。 Square 的初始状态 (i, j) 表示为 S_{i,j},这意味着:
.:这是一个没有墙的正方形。s:这是一个没有围墙的正方形,Snuke就在那里。a:是一个没有墙的正方形,里面有货物。g:是一个没有围墙的正方形,是货物的目的地。#:这是一个有墙的广场,无法参观。
保证网格中恰好有一件货物、一个目的地和一件 Snuke。 Snuke 的目标是将货物运送到目的地。
Snuke 可以执行以下任一动作任意次数:
- 移动到与 Snuke 当前方格垂直或水平相邻的没有货物或墙壁的方格。
- 将与Snuke当前方格相邻的方格中的货物垂直或水平地沿着Snuke货物方向推到下一个没有墙壁的方格,并移动到货物原来所在的方格。
打印 Snuke 实现目标所需的最少移动次数。 如果目标无法实现,则打印 -1 代替。
约束
- H 和 W 是介于 1 和 50,包括在内。
- S_i 是一个长度为的字符串 W 组成
.,s,a,g,和#. - S_{i,j} 恰好包含一个
s,一a,和一个g.
输入
输入由标准输入按以下格式给出:
H W
S_{1,1}S_{1,2}\ldots S_{1,W}
\vdots
S_{H,1}S_{H,2}\ldots S_{H,W}
输出
打印答案。
示例输入 1
3 3 s.. .a. ..g
示例输出 1
5
他可以携带货物 5 通过如下方式移动:
- 向右移动。
- 将货物向下推,向下移动。
- 向左移动。
- 向下移动。
- 将货物向右推,并向右移动。
示例输入 2
4 4 s... .a#. .... ###g
示例输出 2
13
示例输入 3
4 4 ...a .s.. ..g. ....
示例输出 3
-1
如果目标无法实现,请打印 -1.