문제

크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 왼쪽 위칸은 (Sr, Sc)에 있을 때, 이 직사각형의 가장 왼쪽 위칸을 (Fr, Fc)로 이동시키기 위한 최소 이동 횟수를 구해보자.

격자판의 각 칸에는 빈 칸 또는 벽이 있다. 직사각형은 벽이 있는 칸에 있을 수 없다. 또한, 직사각형은 격자판을 벗어날 수 없다.

직사각형은 한 번에 왼쪽, 오른쪽, 위, 아래 중 한 방향으로 한 칸 이동시킬 수 있다.

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

# 1. check_move
# 2. bfs

from collections import deque

INF = 10**9

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
h, w, sr, sc, fr, fc = map(int, input().split())
visited = [[False] * m for _ in range(n)]
visit = [[INF] * m for _ in range(n)]

# 누적합
prefix = [[0] * (m+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        prefix[i][j] = graph[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]

# 직사각형 내부에 벽이 있는지 확인
def check_move(i, j):
    ny, nx = i+h, j+w
    
    if ny < 1 or nx < 1 or ny > n or nx > m:
        return False
    
    check = prefix[ny][nx] - prefix[i][nx] - prefix[ny][j] + prefix[i][j]
    if check:
        return False
    
    return True

# 직사각형 이동
def bfs(y, x):
    queue = deque()
    y, x = y-1, x-1
    queue.append((y, x))
    visit[y][x] = 0
    while queue:
        y, x = queue.popleft()
        if visited[y][x] == False:
            visited[y][x] = True
            
        dy, dx = [-1, 1, 0, 0], [0, 0, -1, 1]
        for i in range(4):
            ny, nx = y + dy[i], x + dx[i]
            if ny < 0 or nx < 0 or ny >= n or nx >= m:
                continue
            if check_move(ny, nx) and visited[ny][nx] == False:
                visit[ny][nx] = min(visit[ny][nx], visit[y][x] + 1)
                queue.append((ny, nx))
                visited[ny][nx] = True
                
bfs(sr, sc)
cnt = visit[fr-1][fc-1]

if cnt == INF:
    cnt = -1
print(cnt)

백준 16973 직사각형 탈출