벽 부수고 이동하기

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Wed Oct  5 23:16:06 2022

@author: kimsubin
"""
from collections import deque
import sys
input = sys.stdin.readline


n, m = map(int, input().split())
graph = [list(map(int, input().strip())) for _ in range(n)]

dx = (-1, 1, 0, 0)
dy = (0, 0, -1, 1)


def bfs():
    q = deque()
    q.append((0, 0, 1))
    visited = [[[0]*2 for _ in range(m)] for _ in range(n)]
    visited[0][0][1] = 1

    while q:
        x, y, w = q.popleft()

        if x == n - 1 and y == m - 1:
            return visited[x][y][w]

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

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

                elif graph[nx][ny] == 0 and visited[nx][ny][w] == 0:
                    visited[nx][ny][w] = visited[x][y][w] + 1
                    q.append((nx, ny, w))
    return -1
print(bfs())