結果
問題 | No.424 立体迷路 |
ユーザー | kichirb3 |
提出日時 | 2018-03-20 10:18:00 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 29 ms / 2,000 ms |
コード長 | 2,181 bytes |
コンパイル時間 | 72 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 11,008 KB |
最終ジャッジ日時 | 2024-07-05 07:15:24 |
合計ジャッジ時間 | 1,404 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 24 ms
10,880 KB |
testcase_01 | AC | 24 ms
10,880 KB |
testcase_02 | AC | 26 ms
10,752 KB |
testcase_03 | AC | 29 ms
10,880 KB |
testcase_04 | AC | 26 ms
10,880 KB |
testcase_05 | AC | 24 ms
10,880 KB |
testcase_06 | AC | 26 ms
10,752 KB |
testcase_07 | AC | 24 ms
10,752 KB |
testcase_08 | AC | 24 ms
11,008 KB |
testcase_09 | AC | 24 ms
10,752 KB |
testcase_10 | AC | 24 ms
10,752 KB |
testcase_11 | AC | 25 ms
11,008 KB |
testcase_12 | AC | 25 ms
10,752 KB |
testcase_13 | AC | 25 ms
10,752 KB |
testcase_14 | AC | 25 ms
10,880 KB |
testcase_15 | AC | 24 ms
10,880 KB |
testcase_16 | AC | 25 ms
10,880 KB |
testcase_17 | AC | 24 ms
10,752 KB |
testcase_18 | AC | 25 ms
10,880 KB |
testcase_19 | AC | 24 ms
10,880 KB |
testcase_20 | AC | 25 ms
11,008 KB |
testcase_21 | AC | 24 ms
10,624 KB |
testcase_22 | AC | 24 ms
10,752 KB |
testcase_23 | AC | 24 ms
11,008 KB |
testcase_24 | AC | 29 ms
11,008 KB |
testcase_25 | AC | 29 ms
11,008 KB |
ソースコード
# -*- coding: utf-8 -*- """ No.424 立体迷路 https://yukicoder.me/problems/no/424 """ import sys from sys import stdin from collections import deque input = stdin.readline def bfs(maze, sx, sy, gx, gy, h, w): explored = [[False] * w for _ in range(h)] # 各マスが探索済かどうかのフラグ Q = deque() Q.append((sx, sy)) while Q: cx, cy = Q.popleft() # 現在地の座標 ch = maze[cy][cx] # 現在のマスの高さ # 隣りの同じ高さのブロックに歩いて移動 または 隣りの±1の高さのブロックにはしごをかけて移動 dx = [0, 0, -1, 1] dy = [-1, 1, 0, 0] for i in range(len(dx)): nx = cx + dx[i] ny = cy + dy[i] if (0 <= nx < w) and (0 <= ny < h) and explored[ny][nx] is False: nh = maze[ny][nx] # 移動先のマスの高さ if ch-1 <= nh <= ch+1: if nx == gx and ny == gy: return 'YES' Q.append((nx, ny)) explored[ny][nx] = True # 2ブロック先の同じ高さのマスにはしごを渡して移動 dx = [0, 0, -2, 2] dy = [-2, 2, 0, 0] for i in range(len(dx)): nx = cx + dx[i] ny = cy + dy[i] if (0 <= nx < w) and (0 <= ny < h) and explored[ny][nx] is False: nh = maze[ny][nx] # 移動先のマスの高さ mh = maze[(ny+cy)//2][(nx+cx)//2] # 間にあるマスの高さ if nh == ch and mh <= ch: if nx == gx and ny == gy: return 'YES' Q.append((nx, ny)) explored[ny][nx] = True return 'NO' def main(args): h, w = map(int, input().split()) sy, sx, gy, gx = map(int, input().split()) # h方向がx、w方向がyなので注意 maze = [] for _ in range(h): maze.append([int(x) for x in list(input().strip())]) ans = bfs(maze, sx-1, sy-1, gx-1, gy-1, h, w) # 入力は1起算なので-1する print(ans) if __name__ == '__main__': main(sys.argv[1:])