結果

問題 No.124 門松列(3)
ユーザー lam6er
提出日時 2025-03-26 15:50:45
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 146 ms / 5,000 ms
コード長 3,345 bytes
コンパイル時間 388 ms
コンパイル使用メモリ 82,084 KB
実行使用メモリ 93,864 KB
最終ジャッジ日時 2025-03-26 15:51:46
合計ジャッジ時間 3,536 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def is_kadomatsu(a, b, c):
    if a == b or b == c or a == c:
        return False
    return (b > a and b > c) or (b < a and b < c)

def main():
    W, H = map(int, sys.stdin.readline().split())
    grid = []
    for _ in range(H):
        row = list(map(int, sys.stdin.readline().split()))
        grid.append(row)
    
    start_x, start_y = 1, 1
    start_val = grid[start_y - 1][start_x - 1]
    goal_x, goal_y = W, H
    
    visited = [[[[-1 for _ in range(10)] for __ in range(10)] for ___ in range(H+2)] for ____ in range(W+2)]
    q = deque()
    q.append((start_x, start_y, 0, 0, 0))  # a=0, b=0 denotes None
    visited[start_x][start_y][0][0] = 0
    
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    answer = -1
    while q:
        x, y, a_prev, b_prev, steps = q.popleft()
        
        if x == goal_x and y == goal_y:
            answer = steps
            break
        
        for dx, dy in directions:
            nx = x + dx
            ny = y + dy
            if 1 <= nx <= W and 1 <= ny <= H:
                new_val = grid[ny-1][nx-1]
                
                # Check Kadomatsu condition if needed
                if a_prev != 0 or b_prev != 0:
                    # Convert 0 to None for checking
                    a = a_prev if a_prev != 0 else None
                    b = b_prev if b_prev != 0 else None
                    if a is not None and b is not None:
                        if not is_kadomatsu(a, b, new_val):
                            continue
                else:
                    # First two steps, no need to check
                    pass
                
                # Compute new_a and new_b
                if a_prev == 0 and b_prev == 0:
                    new_a = start_val
                    new_b = new_val
                else:
                    new_a = b_prev
                    new_b = new_val
                
                # Convert to storage format (0 for None)
                na_stored = new_a if new_a is not None else 0
                nb_stored = new_b if new_b is not None else 0
                # Wait, no, new_a and new_b are computed from previous stored values (0 represents None)
                # Wait, the code above uses a_prev and b_prev which are stored as 0 for None.
                # So when a_prev and b_prev are 0, it's the initial state.
                # After the first move, new_a is start_val, new_b is new_val, which are stored as non-zero.
                # So in the code, the stored a_prev and b_prev are 0 for the initial state.
                # For subsequent states, a_prev and b_prev are non-zero.
                
                # Compute stored new_a and new_b
                if a_prev == 0 and b_prev == 0:
                    stored_new_a = start_val
                    stored_new_b = new_val
                else:
                    stored_new_a = b_prev
                    stored_new_b = new_val
                
                if visited[nx][ny][stored_new_a][stored_new_b] == -1 or steps + 1 < visited[nx][ny][stored_new_a][stored_new_b]:
                    visited[nx][ny][stored_new_a][stored_new_b] = steps + 1
                    q.append((nx, ny, stored_new_a, stored_new_b, steps + 1))
    
    print(answer)

if __name__ == "__main__":
    main()
0