문제

홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이 있어 홍익이가 탈출하기 어렵게 하고 있다.

홍익이는 마법사의 연구실에서 훔친 지팡이가 있어, 벽을 길로 만들 수 있다. 그렇지만, 안타깝게도 마법의 지팡이는 단 한 번만 사용할 수 있다.

이때, 홍익이를 도와 미로에서 탈출할 수 있는지 알아보고, 할 수 있다면 가장 빠른 경로의 거리 D는 얼마인지 알아보자.

인접한 칸으로 이동하는데 똑같은 시간이 들고, 벽을 부수는 데 시간이 걸리지 않는다.

# 14923
import sys
input = lambda: sys.stdin.readline().strip()

from collections import deque

# 1. 벽 1회 부순 경로, 벽을 부수지 않은 경로 리스트
# 2. 빈칸 이동시 벽 1회 부순 경로와 부수지 않은 경로 모두 이동
# 3. 벽 이동시 부수지 않은 경로에서 벽 1회 부순 경로로 이동

n, m = map(int, input().split())
start = list(map(int, input().split()))
end = list(map(int, input().split()))
arr = [list(map(int, input().split())) for _ in range(n)]

start[0], start[1], end[0], end[1] = start[0]-1, start[1]-1, end[0]-1, end[1]-1

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


def bfs(x, y):
    global n, m, end, arr
    broken_dist = [[-1] * m for _ in range(n)]
    dist = [[-1] * m for _ in range(n)]
    
    queue = deque()
    queue.append((x, y))
    broken_dist[x][y], dist[x][y] = 0, 0
    
    while queue:
        x, y = queue.popleft()
        if [x, y] == end:
            continue
            
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue
            
            if arr[nx][ny]:
                if dist[x][y] != -1:
                    if broken_dist[nx][ny] == -1 or dist[x][y] + 1 < broken_dist[nx][ny]:
                        broken_dist[nx][ny] = dist[x][y] + 1
                        queue.append((nx, ny))
                
            else:
                check = False
                
                if dist[x][y] != -1:
                    if dist[nx][ny] == -1 or dist[x][y] + 1 < dist[nx][ny]:
                        dist[nx][ny] = dist[x][y] + 1
                        check = True
                
                
                add_dist = -1
                if broken_dist[x][y] != -1 and dist[x][y] != -1:
                    add_dist = min(broken_dist[x][y], dist[x][y])
                elif broken_dist[x][y] != -1:
                    add_dist = broken_dist[x][y]
                elif dist[x][y] != -1:
                    add_dist = dist[x][y]
                    
                if add_dist != -1:             
                    if broken_dist[nx][ny] == -1 or add_dist + 1 < broken_dist[nx][ny]:
                        broken_dist[nx][ny] = add_dist + 1
                        check = True
                        
                if check:
                    queue.append((nx, ny))
    
    return broken_dist[end[0]][end[1]]


print(bfs(start[0], start[1]))

백준 14923 미로 탈출