結果

問題 No.424 立体迷路
コンテスト
ユーザー lam6er
提出日時 2025-03-20 21:16:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 57 ms / 2,000 ms
コード長 1,891 bytes
コンパイル時間 418 ms
コンパイル使用メモリ 82,792 KB
実行使用メモリ 69,396 KB
最終ジャッジ日時 2025-03-20 21:16:56
合計ジャッジ時間 2,293 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import deque

h, w = map(int, input().split())
s_x, s_y, g_x, g_y = map(int, input().split())
grid = []
for _ in range(h):
    line = input().strip()
    grid.append([int(c) for c in line])

# Check if start is already the goal
if (s_x == g_x) and (s_y == g_y):
    print("YES")
    exit()

# Directions: up, down, left, right (dx, dy)
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

visited = [[False] * (w + 1) for _ in range(h + 1)]
queue = deque()
queue.append((s_x, s_y))
visited[s_x][s_y] = True

found = False

while queue:
    x, y = queue.popleft()
    
    if x == g_x and y == g_y:
        found = True
        break
    
    current_height = grid[x-1][y-1]
    
    for dx, dy in directions:
        # Check 1-step move
        new_x = x + dx
        new_y = y + dy
        if 1 <= new_x <= h and 1 <= new_y <= w:
            if not visited[new_x][new_y]:
                neighbor_height = grid[new_x-1][new_y-1]
                if (neighbor_height == current_height) or \
                   (neighbor_height == current_height + 1) or \
                   (neighbor_height == current_height - 1):
                    visited[new_x][new_y] = True
                    queue.append((new_x, new_y))
        
        # Check 2-step move
        new_x2 = x + 2 * dx
        new_y2 = y + 2 * dy
        if 1 <= new_x2 <= h and 1 <= new_y2 <= w:
            inter_x = x + dx
            inter_y = y + dy
            if 1 <= inter_x <= h and 1 <= inter_y <= w:
                intermediate_height = grid[inter_x-1][inter_y-1]
                target_height = grid[new_x2-1][new_y2-1]
                if intermediate_height < current_height and target_height == current_height:
                    if not visited[new_x2][new_y2]:
                        visited[new_x2][new_y2] = True
                        queue.append((new_x2, new_y2))

print("YES" if found else "NO")
0