← 返回题目列表

AtCoder · past202206_i

I. 清理

中文机器翻译题面 查看原题

分数: 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.