[백준_파이썬]2178번_미로탐색

# 최소의 칸 수 = 최소 이동거리 => bfs
from collections import deque
queue = deque()

# 방향설정
dx = [1, -1, 0, 0]
dy = dx[::-1]

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

def bfs(x, y):
    queue.append((x,y))

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 범위 안에 있고,
            if 0 <= nx < n and 0 <= ny < m:
                # 갈 수 있는 길이면
                if graph[nx][ny] == 1:
                    # 해당 길에 이전의 좌표에있는 값을 더해주기(이래서 bfs는 간선의 비용이 동일할 때만 사용 가능하다는 것)
                    # 그래야 마지막 지점에 도착했을 때, 모두 더한 값이 총 거리가 되니까
                    graph[nx][ny] = graph[x][y] + 1
                    queue.append((nx, ny))
    
    # 처음에 1,1 부터 시작한다고 했으므로 0인덱스는 생각하지 않았기에 -1해주기
    return graph[n-1][m-1]
# graph = []

# for _ in range(n):
#     graph.append(list(map(int, input())))
# 위의 두 줄을 아래와 같이 한 줄로 사용 가능
graph = [list(map(int, input())) for _ in range(n)]

print(bfs(0,0))