PAST202005-G グリッド金移動
https://gyazo.com/2f9a1f2b02a0ee4fd8b097c96a938b32
昔はACで、1000msだったのが今回は2000msオーバーだったので原因をしらべてたら
if文の判定が2つあるとき、どっちを先に置くかで実行時間が倍違っていた。。
if visited[x][y] or (x, y) in wallsの箇所
(x, y) in wallsはwallsが大きなサイズの場合探索時間が線形に増えそう
visited[x][y]は辞書索引な引き方なので実行速度は一定ぽい
と思ってvisitedを先に置いたところ、1000ms程度に収まってACtada.icon
https://gyazo.com/cb18caa4abf5101f799aa526e29e695c
code:solution.py
from collections import deque
def solve(N, X, Y, walls):
Q = deque()
# (start_x, start_y, step)
Q.append((0, 0, 0))
visited = []
for _ in range(403):
visited.append(False * 403) while 0 < len(Q):
x, y, step = Q.popleft()
if x == X and y == Y:
print(step)
return
if visitedxy or (x, y) in walls: continue
next_xys = [
(x+1, y+1),
(x, y+1),
(x-1, y+1),
(x+1, y),
(x-1, y),
(x, y-1),
]
for nx, ny in next_xys:
if -201 <= nx <= 201 and -201 <= ny <= 201:
if not visitednxny and (nx, ny) not in walls: Q.append((nx, ny, step+1))
print(-1)
def main():
N, X, Y = map(int, input().split())
walls = []
for _ in range(N):
walls.append(tuple(map(int, input().split())))
solve(N, X, Y, walls)
if __name__ == '__main__':
main()