結果

問題 No.424 立体迷路
ユーザー ThetaTheta
提出日時 2022-12-06 19:00:43
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 31 ms
11,008 KB
testcase_01 AC 30 ms
10,880 KB
testcase_02 AC 29 ms
10,880 KB
testcase_03 AC 29 ms
10,880 KB
testcase_04 AC 29 ms
11,008 KB
testcase_05 AC 28 ms
11,008 KB
testcase_06 AC 28 ms
10,880 KB
testcase_07 AC 30 ms
10,880 KB
testcase_08 AC 29 ms
11,008 KB
testcase_09 AC 28 ms
10,880 KB
testcase_10 AC 27 ms
11,008 KB
testcase_11 AC 30 ms
10,880 KB
testcase_12 AC 29 ms
11,008 KB
testcase_13 AC 28 ms
11,008 KB
testcase_14 AC 28 ms
11,008 KB
testcase_15 AC 28 ms
10,880 KB
testcase_16 AC 30 ms
11,008 KB
testcase_17 AC 31 ms
11,136 KB
testcase_18 AC 31 ms
11,264 KB
testcase_19 AC 32 ms
11,136 KB
testcase_20 AC 31 ms
11,136 KB
testcase_21 AC 30 ms
10,880 KB
testcase_22 AC 29 ms
10,880 KB
testcase_23 AC 29 ms
10,880 KB
testcase_24 AC 41 ms
11,264 KB
testcase_25 AC 41 ms
11,264 KB
権限があれば一括ダウンロードができます

ソースコード

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