[伯俊]2178号迷宮を探る
質問する
https://www.acmicpc.net/problem/2178
に答える
これはBFSでアクセスする問題です.
時間の複雑さを減らすために,Dequeとともにアクセスするか否かを示す辞書を用いた.
from collections import deque
#입력
n, m = map(int, input().split())
arr = [input() for _ in range(n)]
dir = [(0, 1), (1, 0), (0, -1), (-1, 0)]
visited = [[False] * m for _ in range(n)] # 방문 상태
queue = deque()
queue.append([0, 0])
visited[0][0] = True
distance = [[0] * m for _ in range(n)]
distance[0][0] = 1 #거리기록
while queue:
curX, curY = queue.popleft()
for dx, dy in dir:
if 0 <= curX + dx < n and 0 <= curY + dy < m:
if arr[curX+dx][curY+dy] == '1' and visited[curX+dx][curY+dy] == False:
visited[curX+dx][curY+dy] = True
distance[curX+dx][curY+dy] = distance[curX][curY] + 1
queue.append([curX+dx, curY+dy])
print(distance[n-1][m-1])
Reference
この問題について([伯俊]2178号迷宮を探る), 我々は、より多くの情報をここで見つけました https://velog.io/@dldbdud314/백준-2178번.-미로탐색テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol