# 직사각형 탈출 - BOJ

# 문제

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

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

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

[입력]

첫째 줄에 격자판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 격자판의 각 칸의 정보가 주어진다. 0은 빈 칸, 1은 벽이다.

마지막 줄에는 직사각형의 크기 H, W, 시작 좌표 Sr, Sc, 도착 좌표 Fr, Fc가 주어진다.

격자판의 좌표는 (r, c) 형태이고, r은 행, c는 열이다. 1 ≤ r ≤ N, 1 ≤ c ≤ M을 만족한다.

[출력]

첫째 줄에 최소 이동 횟수를 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.

[제한]

2 ≤ N, M ≤ 1,000 1 ≤ H ≤ N 1 ≤ W ≤ M 1 ≤ Sr ≤ N-H+1 1 ≤ Sc ≤ M-W+1 1 ≤ Fr ≤ N-H+1 1 ≤ Fc ≤ M-W+1

입력으로 주어진 직사각형은 격자판을 벗어나지 않고, 직사각형이 놓여 있는 칸에는 벽이 없다.

# 풀이

직사각형이 만들어지는 테두리만 BFS로 돌면서 탐색

from collections import deque

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

N, M = map(int, input().split())
board = [list(input().split()) for _ in range(N)]
visit = [[False] * M for _ in range(N)]
H, W, Sr, Sc, Fr, Fc = map(int, input().split())
Sr -= 1
Sc -= 1
Fr -= 1
Fc -= 1

start = (Sr, Sc, 0)
des = (Fr, Fc)
cnt = 0

q = deque()
q.append(start)

while q:
    y, x, cnt = q.popleft()
    if (y, x) == des:
        print(cnt)
        exit(0)
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= M or ny >= N:
            continue
        flag = False
        if visit[ny][nx] == False:
            if 1 <= ny + H - 1 < N and 1 <= nx + W - 1 < M:
                for row in (board[ny], board[ny + H - 1]):
                    if '1' in row[nx:nx+W]:
                        flag = True
                        break
                for row in board[ny:ny + H]:
                    if row[nx] == '1' or row[nx + W - 1] == '1':
                        flag = True
                        break
                if flag == False:
                    visit[ny][nx] = True
                    q.append((ny, nx, cnt + 1))
print(-1)