結果

問題 No.424 立体迷路
コンテスト
ユーザー Theta
提出日時 2022-12-06 19:00:43
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 41 ms / 2,000 ms
コード長 2,639 bytes
コンパイル時間 93 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 11,264 KB
最終ジャッジ日時 2024-10-13 08:02:02
合計ジャッジ時間 2,068 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

from itertools import product


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

    def up_coord(cur):
        if cur[0] == 0:
            return
        return cur[0]-1, cur[1]

    def down_coord(cur):
        if cur[0] == h-1:
            return
        return cur[0]+1, cur[1]

    def left_coord(cur):
        if cur[1] == 0:
            return
        return cur[0], cur[1]-1

    def right_coord(cur):
        if cur[1] == w-1:
            return
        return cur[0], cur[1]+1

    visited = set()
    searching = set()
    unvisited = set(product(range(h), range(w)))
    searching.add((sx, sy))
    unvisited.remove((sx, sy))

    def normal_move(current_, cand):
        if abs(b[cand[0]][cand[1]] - b[current_[0]][current_[1]]) <= 1:
            try:
                unvisited.remove(cand)
                searching.add(cand)
            except KeyError:
                pass

    def can_bridge_over(current_, cand):
        return b[cand[0]][cand[1]] < b[current_[0]][current_[1]]

    def bridge_move(current_, mid, cand):
        if not can_bridge_over(current_, mid):
            return

        if b[current_[0]][current_[1]] == b[cand[0]][cand[1]]:
            try:
                unvisited.remove(cand)
                searching.add(cand)
            except KeyError:
                pass

    while searching:
        if (gx, gy) in searching:
            print("YES")
            return

        current = searching.pop()
        if (current_left := left_coord(current)) is not None:
            normal_move(current, current_left)

            if (current_ll := left_coord(current_left)) is not None:
                bridge_move(current, current_left, current_ll)

        if (current_right := right_coord(current)) is not None:
            normal_move(current, current_right)

            if (current_rr := right_coord(current_right)) is not None:
                bridge_move(current, current_right, current_rr)

        if (current_up := up_coord(current)) is not None:
            normal_move(current, current_up)

            if (current_uu := up_coord(current_up)) is not None:
                bridge_move(current, current_up, current_uu)

        if (current_down := down_coord(current)) is not None:
            normal_move(current, current_down)

            if (current_dd := down_coord(current_down)) is not None:
                bridge_move(current, current_down, current_dd)

    print("NO")


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