結果

問題 No.424 立体迷路
ユーザー ThetaTheta
提出日時 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()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0