/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 6 点
問題文
縦 H 行、横 W 列の長方形のマス目が与えられます。上から i 番目、左から j 番目のマスをマス (i,j) と呼びます。
各マスは、「壁のないマス」、「壁があるマス」のいずれかです。マス (i,j) の初期状態の情報は S_{i,j} で表され、以下を意味します。
.：壁のないマスである。s：壁のないマスであり、すぬけ君がいる。a：壁のないマスであり、荷物がある。g：壁のないマスであり、片付け先である。#：壁があるマスであり、通ることができない。
荷物と片付け先のマスはちょうど 1 個ずつあり、すぬけ君はちょうど 1 人であることが保証されます。すぬけ君の目標は荷物を片付け先のマスに運ぶことです。
すぬけ君は以下のいずれかの行動を何回でも行うことができます。
- 今いるマスと上下左右に隣接している、荷物も壁もないマスに移動する。
- 今いるマスと上下左右に隣接しているマスにある荷物を、すぬけ君から見て1つ奥の壁のないマスに押して動かし、動かした荷物があったマスに移動する。
すぬけ君が目標を達成するために必要な行動回数の最小値を出力してください。ただし、目標が達成不可能な場合は -1 を出力してください。
制約
- H,W は 1 以上 50 以下の整数
- S_i は
.,s,a,g,#からなる長さ W の文字列 - S_{i,j} の中に
s,a,gはそれぞれちょうど 1 個ずつ含まれる
入力
入力は以下の形式で標準入力から与えられる。
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 を出力してください。
Score : 6 points
Problem Statement
You are given a rectangular grid with H horizontal rows and W vertical columns. The square at the i-th row from the top and the j-th column from the left is called Sqaure (i, j).
Each square is either a "square without a wall" or a "square with a wall". The initial state of Square (i, j) is represented by S_{i,j}, which means:
.: it is a square without a wall.s: it is a square without a wall, and Snuke is there.a: it is a square without a wall, and there is a cargo in it.g: it is a square without a wall, and is a destination of the cargo.#: it is a square with a wall, which cannot be visited.
It is guaranteed that there is exactly one cargo, one destination, and one Snuke in the grid. Snuke's objective is to carry the cargo to the destination.
Snuke can do one of the following moves any number of times:
- Move to a square, without the cargo or a wall, vertically or horizontally adjacent to Snuke's current square.
- Push the cargo in the square vertically or horizontally adjacent to Snuke's current square to the next square without a wall in the direction of the cargo from Snuke, and move to the square that the cargo was originally in.
Print the minimum number of moves required for Snuke to achieve the objective. If the objective is unachievable, print -1 instead.
Constraints
- H and W are integers between 1 and 50, inclusive.
- S_i is a string of length W consisting of
.,s,a,g, and#. - S_{i,j} contains exactly one
s, onea, and oneg.
Input
Input is given from Standard Input in the following format:
H W
S_{1,1}S_{1,2}\ldots S_{1,W}
\vdots
S_{H,1}S_{H,2}\ldots S_{H,W}
Output
Print the answer.
Sample Input 1
3 3 s.. .a. ..g
Sample Output 1
5
He can carry the cargo with 5 moves by moving as follows:
- Move to the right.
- Push the cargo downward, and move downward.
- Move to the left.
- Move downward.
- Push the cargo to the right, and move to the right.
Sample Input 2
4 4 s... .a#. .... ###g
Sample Output 2
13
Sample Input 3
4 4 ...a .s.. ..g. ....
Sample Output 3
-1
If the objective is unachievable, print -1.