from collections import deque
maps = [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]
# maps = [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]]
n = len(maps)
m = len(maps[0])
dr = [1,-1,0,0]
dc = [0,0,1,-1]
visited = [[False]*m for _ in range(n)]
dist = [[0]*m for _ in range(n)]
def BFS_dist(start): # start = (r,c)
r,c = start
visited[r][c]=True
dist[r][c]=1
q = deque([start])
while q:
r,c = q.popleft()
if (r,c)==(n-1,m-1):
return dist[r][c]
for i in range(4):
nr, nc = r+dr[i], c+dc[i]
if 0<=nr<n and 0<=nc<m and not visited[nr][nc] and maps[nr][nc]==1:
visited[nr][nc]=True
dist[nr][nc] = dist[r][c]+1
q.append((nr,nc))
# return 이 안된 경우 target 도착 못한 case
return -1
print(BFS_dist((0,0)))
