第二回 PAST H - 1-9 Grid
問題原文
問題要旨
S
, G
がひとつずつ、それと 1
~ 9
で構成される のグリッドが与えられる。
上下左右への移動を繰り返して、S
から G
へ向かう時、 1
~ 9
のマスを 1
, 2
... 9
の順番に踏んでいるようなものの最小の移動回数を求めよ。
そのような経路が存在しない場合は -1
とせよ。
ただし、同じマスを複数回通って良く, S
, G
も途中で通っても良い。 1
の次 2
を踏む必要はなくて、 1 5678 2
みたいな移動でももちろんOK。ただしこの場合には途中に通った 5678
は条件を満たした扱いにならない。
解法
とりあえず、 S
を 0
, G
を 10
にエンコードした。
そのあと、なんとか状態の同一視をやりたいな〜という気分になって、
マス にいて、最後にチェックした条件を満たすような数字が であるような状態になるための最小移動回数
というdpテーブルを定義してみた。で、なんとなくできそうなのでこの方針でいくことに。
更新順がわかんないので、メモ化再帰でなんとなく G
から埋めて行きました。
実装
結構苦戦した。
結局次の数字のマスにしか遷移してないので、dpの の部分は持たなくてよかったね多分。
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))
感想
これを解いて上級を確定させた。
普通にこの後出てくる問題より難しかった気がするぞ。。。