結果

問題 No.124 門松列(3)
コンテスト
ユーザー ntuda
提出日時 2025-08-16 09:49:43
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 68 ms / 5,000 ms
コード長 1,112 bytes
コンパイル時間 339 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 73,036 KB
最終ジャッジ日時 2025-08-16 09:49:46
合計ジャッジ時間 3,107 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

W,H = map(int,input().split())
M = [list(map(int,input().split())) for _ in range(H)]
dir = [[0,1],[1,0],[-1,0],[0,-1]]
INF = 10 ** 4
def dfs(a):
    Q = [(0,0,-1)]
    Q2 = []
    nv = [[0] * W for _ in range(H)]
    nv[0][0] = 1
    cnt = 0
    while Q:
        while Q:
            x,y,z = Q.pop()
            if x == H-1 and y == W - 1:
                return cnt
            v = M[x][y]
            for dx,dy in dir:
                x2 = x + dx
                y2 = y + dy
                if 0 <= x2 < H and 0 <= y2 < W:
                    if nv[x2][y2] == 2:
                        continue
                    if a == 1:
                        if v > M[x2][y2] and M[x2][y2] != z:
                            nv[x2][y2] += 1
                            Q2.append((x2,y2,M[x][y]))
                    else:
                        if v < M[x2][y2] and M[x2][y2] != z:
                            nv[x2][y2] += 1
                            Q2.append((x2,y2,M[x][y]))
        a ^= 1
        cnt += 1
        Q,Q2 = Q2,Q
    return INF

a = min(dfs(0),dfs(1))
if a == INF:
    print(-1)
else:
    print(a)
0