백준 2178번 - 미로 탐색

# 입력
import sys
read = sys.stdin.readline

n,m = map(int, read().split())
maze = []
for _ in range(n):
  maze.append(list(map(int,read().strip())))

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

# 처리 - bfs 활용

def bfs(x, y):
  from collections import deque
  queue = deque()
  queue.append((x,y))

  while queue:
    x,y = queue.popleft()
    for i in range(4):
      new_x = x+dx[i]
      new_y = y+dy[i]

      if 0<=new_x<n and 0<=new_y<m and maze[new_x][new_y] == 1:
        queue.append((new_x,new_y))
        maze[new_x][new_y] = maze[x][y] + 1

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