結果
問題 | No.424 立体迷路 |
ユーザー |
|
提出日時 | 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 |
ソースコード
from itertools import productdef 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:returnreturn cur[0]-1, cur[1]def down_coord(cur):if cur[0] == h-1:returnreturn cur[0]+1, cur[1]def left_coord(cur):if cur[1] == 0:returnreturn cur[0], cur[1]-1def right_coord(cur):if cur[1] == w-1:returnreturn cur[0], cur[1]+1visited = 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:passdef 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):returnif b[current_[0]][current_[1]] == b[cand[0]][cand[1]]:try:unvisited.remove(cand)searching.add(cand)except KeyError:passwhile searching:if (gx, gy) in searching:print("YES")returncurrent = 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()