結果

問題 No.124 門松列(3)
コンテスト
ユーザー ckawatak
提出日時 2019-01-19 17:19:09
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,436 bytes
コンパイル時間 162 ms
コンパイル使用メモリ 82,440 KB
実行使用メモリ 849,232 KB
最終ジャッジ日時 2024-07-18 02:56:27
合計ジャッジ時間 11,900 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other MLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

W,H = list(map(int, input().split(' ')))

G = []
for i in range(H):
    G.append(list(map(int, input().split(' '))))

distance = []
for i in range(H):
    distance.append([float('inf') for _ in range(W)])

def is_kadomatsu(path, next):
    current = path.copy()
    
    if len(current) == 3:
        current.popleft()        
    current.append(next)
    
    if len(current) < 3:
        return current

    if current[0] == current[1] \
        or current[1] == current[2] \
            or current[0] == current[2]:
        return []

    sorted_current = sorted(current, reverse=True)

    return current if current[1] == sorted_current[0] \
        or current[1] == sorted_current[2] else []

def bfs():
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    que = deque()
    path = deque()

    path.append(G[0][0])
    que.append((path,0,0))
    distance[0][0] = 0

    while len(que) != 0:
        p,x,y = que.popleft()
        if x == H-1 and y == W-1:
            break
        for i in range(len(dx)):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx and 0 <= ny and nx < W and ny < H:
                np = is_kadomatsu(p,G[nx][ny])
                if np:
                    que.append((np,nx,ny))
                    distance[nx][ny] = distance[x][y] + 1

    return distance[H-1][W-1]

answer = bfs()
if answer == float('inf'):
    print(-1)
else:
    print(answer)
0