AT274の技術だったりなかったり

あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。

第二回 PAST H - 1-9 Grid

問題原文

atcoder.jp

問題要旨

S, G がひとつずつ、それと 1 ~ 9 で構成される  H × W のグリッドが与えられる。 上下左右への移動を繰り返して、S から G へ向かう時、 1 ~ 9 のマスを 1, 2 ... 9 の順番に踏んでいるようなものの最小の移動回数を求めよ。
そのような経路が存在しない場合は -1 とせよ。
ただし、同じマスを複数回通って良く, S, G も途中で通っても良い。 1 の次 2 を踏む必要はなくて、 1 5678 2 みたいな移動でももちろんOK。ただしこの場合には途中に通った 5678 は条件を満たした扱いにならない。

  •  1 \leq H, W \leq 50

解法

とりあえず、 S0, G10エンコードした。

そのあと、なんとか状態の同一視をやりたいな〜という気分になって、  dp[h\rbrack[w\rbrack[k\rbrack := マス  (h, w) にいて、最後にチェックした条件を満たすような数字が  k であるような状態になるための最小移動回数
というdpテーブルを定義してみた。で、なんとなくできそうなのでこの方針でいくことに。

更新順がわかんないので、メモ化再帰でなんとなく G から埋めて行きました。

実装

結構苦戦した。
結局次の数字のマスにしか遷移してないので、dpの  k の部分は持たなくてよかったね多分。

import sys
sys.setrecursionlimit(10 ** 9)
H, W = map(int, input().split())
G = [list(input()) for _ in range(H)]
P = {i: [] for i in range(11)}
 
# S: 0, G: 10にエンコード。ついでにGのindex取得。あと出現位置記録
Gh, Gw = None, None
for h in range(H):
    for w in range(W):
        if G[h][w] == 'S':
            G[h][w] = 0
        if G[h][w] == 'G':
            Gh, Gw = h, w
            G[h][w] = 10
 
        P[int(G[h][w])].append((h, w))
 
for h in range(H):
    G[h] = list(map(int, G[h]))
 
for v in P.values():
    if not v:
        print(-1)
        exit()
 
# dp[h][w][k] := マス(h, w)にいて、最後にチェックした(1~9の並びにカウントした)マスがkであるようなものの最小移動回数
dp = [[[float('inf')] * 11 for w in range(W)] for h in range(H)]
 
 
def dfs(nh, nw, k):
    if k == 0:
        return 0
 
    if dp[nh][nw][k] != float('inf'):
        return dp[nh][nw][k]
 
    ret = float('inf')
    for ph, pw in P[k - 1]:
        ret = min(ret, dfs(ph, pw, k - 1) + abs(nh - ph) + abs(nw - pw))
 
    dp[nh][nw][k] = ret
    return ret
 
 
print(dfs(Gh, Gw, 10))

感想

これを解いて上級を確定させた。
普通にこの後出てくる問題より難しかった気がするぞ。。。