yukicoder No.124 門松列(3)

答えがわかってしまえば簡単なのだが、自力で思いつけなかった。勉強になる。

問題はこちら。

問題

WxHの平面があり、各マスに1から9のどれかが割り振られている。この平面上では上下左右の方向に移動することができるが、移動後の直近3回のマスの値が門松列の条件(すべての値が異なり、2番めに小さい数が2番めに位置しない）を満たしている場合のみにしか移動は許されない。この条件のもとで、左上からスタートして右下に移動するの必要な最小ステップはいくらか。辿りつけない場合は-1を出力する。H,W ≦ 100。

解法

次に行ける場所は、今の座標と前の場所の値によって決まっていく。よって、前にいた場所の値と今の座標を持ってBFSで移動していき、[前にいた場所の値][今の座標] = (最小ステップ数) を計算していけばいい。BFSなので一度コスト表に値が入れば、そこを通る場合はそれ以上計算しなくて済む。

BFSなのだろうとはわかったが、次に行ける場所は今の座標と前の場所の値によって決まっていくのだから、それに対応したコスト表を持てばいいことに気づけなかった。へんに考えずに状態に対応したコスト表を持てばいい、のかな。

import sys
sys.setrecursionlimit(100000)

dxy = zip([1,0,-1,0],[0,1,0,-1])

def isKadomatsu(a,b,c):
    if a == 0 or b == 0: return True
    return b < a < c or b < c < a or a < c < b or c < a < b

W,H = map(int,raw_input().split())
M = [map(int,raw_input().split()) for i in xrange(H)]
que = [[0,0,0]]
cost = [[[-1]*W for i in xrange(H)] for j in xrange(10)]
cost[0][0][0] = 0

while que:
    w,h,bef = que.pop(0)
    if (w,h) == (W-1,H-1):
        print cost[bef][h][w]
        break
    cur = M[h][w]
    for dx,dy in dxy:
        nw,nh = w+dx,h+dy
        if not (0 <= nw < W and 0 <= nh < H): continue
        aft = M[nh][nw]
        if not isKadomatsu(bef, cur, aft): continue
        if cost[cur][nh][nw] != -1: continue
        cost[cur][nh][nw] = cost[bef][h][w]+1
        que.append([nw,nh,cur])
else:
    print -1