結果

問題 No.424 立体迷路
コンテスト
ユーザー cologne
提出日時 2025-12-11 13:34:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 71 ms / 2,000 ms
コード長 1,105 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 586 ms
コンパイル使用メモリ 82,356 KB
実行使用メモリ 67,704 KB
最終ジャッジ日時 2025-12-11 13:34:10
合計ジャッジ時間 3,339 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from collections import deque


def input(): return sys.stdin.readline().rstrip('\n')


def main():
    h, w = map(int, input().split())
    sx, sy, gx, gy = map(lambda x: int(x) - 1, input().split())
    a = [list(map(int, input())) for _ in range(h)]

    q = deque([(sx, sy)])
    inq = {(sx, sy)}
    while q:
        x, y = q.popleft()
        if (x, y) == (gx, gy):
            return 'YES'
        for (dx, dy) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            if 0 <= x + dx < h and 0 <= y + dy < w and (x + dx, y + dy) not in inq and abs(
                    a[x][y] - a[x + dx][y + dy]) <= 1:
                inq.add((x + dx, y + dy))
                q.appendleft((x + dx, y + dy))
            if 0 <= x + 2 * dx < h and 0 <= y + 2 * dy < w and (x + 2 * dx, y + 2 * dy) not in inq and a[x + dx][
                y + dy] < a[x][y] and a[x + 2 * dx][y + 2 * dy] == a[x][y]:
                inq.add((x + 2 * dx, y + 2 * dy))
                q.appendleft((x + 2 * dx, y + 2 * dy))

    return 'NO'


if __name__ == '__main__':
    ret = main()
    if ret is not None:
        print(ret)
0