BOJ - 14923 - 미로 탈출

import sys
from collections import deque

def BFS(maps, N, M, sx, sy, ex, ey):
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    visit = [[[0] * 2 for _ in range(M)] for _ in range(N)]
    visit[sx][sy][1] = 1
    Q = deque()
    Q.append((sx, sy, 1))

    while Q:
        x, y, wall = Q.popleft()
        if x == ex and y == ey:
            return visit[ex][ey][wall] - 1

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

            if 0 <= nx < N and 0 <= ny < M:
                if maps[nx][ny] == 1 and wall == 1:
                    visit[nx][ny][0] = visit[x][y][1] + 1
                    Q.append((nx, ny, 0))
                elif maps[nx][ny] == 0 and visit[nx][ny][wall] == 0:
                    visit[nx][ny][wall] = visit[x][y][wall] + 1
                    Q.append((nx, ny, wall))
        
    return -1

def solution():
    N, M = map(int, sys.stdin.readline().split())
    sx, sy = map(int, sys.stdin.readline().split())
    ex, ey = map(int, sys.stdin.readline().split())

    maps = []
    for _ in range(N):
        maps.append(list(map(int, list(sys.stdin.readline().split()))))

    print(BFS(maps, N, M, sx - 1, sy - 1, ex - 1, ey - 1))

solution()

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