Problem:

Problem C: Changing Grids

Background

  A君とB君は、『Changing Grids』というゲームに熱中している。このゲームは2人用で、プレイヤー1がステージを構成し、プレイヤー2がそのステージに挑戦しゴールを目指すというものである。

  今、A君とB君はこのゲームを何度かプレイしているが、A君の連勝でB君は1度も勝つことができていない。そこであなたは、B君にこのゲームを攻略するためのヒントを教えてあげることにした。

Problem

時刻T0 = 0における縦H&times;横Wの大きさの二次元グリッドの状態がArea0として与えられる。次に、このグリッドの状態は時刻Tiにおいて、状態Areaiに切り替わる。この切り替わる過程はN回繰り返される。初期状態のグリッドにはスタートの位置'S'とゴールの位置'G'が与えられる。いずれかのグリッドにおいてゴールへ辿り着ける場合は、そのときの最小歩数を出力し、ゴールへ辿り着けない場合は、'-1'を出力せよ。なお、以下の条件も満たす必要がある。

Areaiは以下の要素で構成されている。

 
‘.’は何もなく移動可能なマス

 
’#’は障害物であり、移動不可能なマス

 
'S'はスタート位置を表すマス

 
'G'はゴール位置を表すマス

プレイヤーは現在いるマスの隣接している上下左右のいずれか1マスに移動する、または現在いるマスに留まるのに1秒かかる。ただし、障害物のマスやグリッドの範囲外には移動できない。

歩数は、現在プレイヤーがいるマスから上下左右のマスへ1マス進むと1増加する。その場に留まる場合には増加しない。

全てのグリッドの大きさは縦H&times;横Wである。

1マス移動、またはその場に留まった後にグリッドが切り替わる際、次のグリッドにおいて障害物が存在しないマスであれば今のグリッドの状態に関わらず移動が可能である。

全てのグリッドにおいて、初期のグリッドに与えられたゴール位置に到達した場合ゴールとみなす。

Input

入力は以下の形式で与えられる。

H W
Area0
N
T1
Area1
T2
Area2
.
.
TN
AreaN

1行目に2つの整数H,Wが空白区切りで与えられる。これは、それぞれ二次元グリッドの縦と横の大きさを表す。2行目からH+1行目までの各行に初期状態の二次元グリッドの状態が与えられる。H+2行目に整数Nが与えられる。これは、二次元グリッドの変化する回数を表す。H+3行目以降にN個の二次元グリッドの切り替わる時刻Tiとその状態が与えられる。ただし、Tiは全て整数である。

Constraints

入力は以下の条件を満たす。

2 ≤ H,W ≤ 20

1 ≤ N ≤ 15

1 ≤ Ti ≤ 200 (T1 < T2 < ... < TN)

スタート位置'S'とゴール位置'G'はそれぞれ初期の二次元グリッドに1つだけ存在する。

Output

スタートからゴールへ到達するための最小の歩数を出力せよ。ただし、ゴールに到達できない場合は'-1'を出力せよ。

Sample Input 1

2 2
S.
.G
1
3
##
##

Sample Output 1

2

1番目のグリッドに切り替わる時刻T1は3であり、時間内にプレイヤーはスタートからゴールまでの最短歩数が2歩で辿り着くことが可能なので2を出力する。

Sample Input 2

2 2
S.
.G
1
2
##
##

Sample Output 2

-1

Sample Input 3

2 3
S##
##G
4
2
###
.##
3
###
#.#
5
###
##.
7
###
###

Sample Output 3

3

Sample Input 4

4 3
S..
...
.G.
...
4
2
###
#.#
###
#.#
4
###
#..
#..
###
6
###
#.#
###
#..
8
###
#..
#..
###

Sample Output 4

3

Sample Input 5

3 3
S##
###
##G
1
1
...
...
...

Sample Output 5

4



Sample input:
2 2
S.
.G
1
3
##
##


Sample output:
2

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

h, w = map(int, input().split())


def get_area():
    mp = ["#" * (w + 2)]
    for _ in range(h):
        mp.append("#" + input() + "#")
    mp.append("#" * (w + 2))
    return mp


areas = [get_area()]
times = {}
n = int(input())
for i in range(n):
    times[int(input())] = i + 1
    areas.append(get_area())

for y in range(1, h + 1):
    for x in range(1, w + 1):
        if areas[0][y][x] == "S":
            sx, sy = x, y
        if areas[0][y][x] == "G":
            gx, gy = x, y

que = []
heappush(que, (0, 0, sx, sy, 0))
dic = {}
dic[(0, sx, sy)] = 0
vec = ((1, 0), (0, -1), (-1, 0), (0, 1))
checked = [[False] * (w + 2) for _ in range(h + 2)]
while que:
    score, time, x, y, area_num = heappop(que)
    if (x, y) == (gx, gy):
        print(score)
        break
    time += 1
    if time in times:
        area_num += 1

    area = areas[area_num]
    for dx, dy in vec:
        nx, ny = x + dx, y + dy
        if area[ny][nx] == "#" :continue
        if (time, nx, ny) not in dic:
            if area_num != n:
                dic[(time, nx, ny)] = score + 1
                heappush(que, (score + 1, time, nx, ny, area_num))
            elif not checked[ny][nx]:
                dic[(time, nx, ny)] = score + 1
                checked[ny][nx] = True
                heappush(que, (score + 1, time, nx, ny, area_num))
    if area[y][x] != "#" and not checked[y][x] and ((time, x, y) not in dic or dic[(time, x, y)] > score):
        dic[(time, x, y)] = score
        heappush(que, (score, time, x, y, area_num))
        if area_num == n:checked[y][x] = True
else:
    print(-1)