2178_미로탐색

ylab 2022. 10. 25. 23:55

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

www.acmicpc.net

from collections import deque

n,m = map(int,input().split())


graph = [list(map(int,input())) for i in range(n)]

visited = [[0]*m for i in range(n)]

dx = [1,-1,0,0]
dy=[0,0,1,-1]


def bfs(x,y):
    q=deque([(x,y)])

    visited[x][y] =1

    while q:
        x,y = q.popleft()
        for j in range(4):
            nx = x+dx[j]
            ny = y+dy[j]

            if 0<=nx<n and 0<=ny<m and graph[nx][ny]==1:
                if visited[nx][ny] == 0 or visited[nx][ny] > visited[x][y]+1:
                    q.append((nx,ny))
                    visited[nx][ny] = visited[x][y]+1

    return
bfs(0,0)
print(visited[n-1][m-1])