[伯俊]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])