[백준] 16973. 직사각형 탈출

크기가 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
• 입력으로 주어진 직사각형은 격자판을 벗어나지 않고, 직사각형이 놓여 있는 칸에는 벽이 없다.

---

예제 입력 1

4 5
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
2 2 1 1 1 4

예제 출력 1

7

아래, 아래, 오른쪽, 오른쪽, 오른쪽, 위, 위

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static int N, M;
    public static int H, W;
    public static int[][] arr;
    public static Position start;
    public static Position end;
    public static boolean[][] visited;
    public static class Position {
        int r;
        int c;
        int count;
        public Position(int r, int c, int count) {
            this.r = r;
            this.c = c;
            this.count = count;
        }
    }
    public static int[] dr = {-1, 1, 0, 0};
    public static int[] dc = {0, 0, -1, 1};

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N][M];
        visited = new boolean[N][M];
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < M; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        st = new StringTokenizer(br.readLine());

        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());
        start = new Position(Integer.parseInt(st.nextToken())-1,Integer.parseInt(st.nextToken())-1, 0);
        end = new Position(Integer.parseInt(st.nextToken())-1,Integer.parseInt(st.nextToken())-1, 0);

        Queue<Position> queue = new LinkedList<>();
        queue.add(start);
        visited[start.r][start.c] = true;

        int result = Integer.MAX_VALUE;
        while (!queue.isEmpty()) {
            Position current = queue.poll();
            if(current.r == end.r && current.c == end.c) {
                result = current.count;
                break;
            }

            for(int i = 0; i < 4; i++) {
                int nr = current.r + dr[i];
                int nc = current.c + dc[i];


                if(nr >= 0 && nc >= 0 && nr <= N - H && nc <= M - W && !visited[nr][nc]) {
                    if (wallCheck(nr, nc)) {
                        continue;
                    }
                    visited[nr][nc] = true;
                    queue.offer(new Position(nr, nc, current.count + 1));
                }
            }

        }
        System.out.println(result == Integer.MAX_VALUE ? -1 : result);
    }

    public static boolean wallCheck(int nr, int nc) {
        for(int j = nc; j < nc + W; j++) {
            if(arr[nr][j] == 1 || arr[nr + H - 1][j] == 1) {
                return true;
            }
        }
        for(int j = nr; j < nr + H; j++) {
            if(arr[j][nc] == 1 || arr[j][nc + W - 1] == 1) {
                return true;
            }
        }
        return false;
    }
}