백준 16973 (직사각형 탈출) - java

 

import java.util.*;
import java.io.*;
import java.awt.Point;
public class Main {
    static int n = 0;
    static int m = 0;
    static int h = 0;
    static int w = 0;
    static int[][] board = new int[1001][1001] ;
    static int[][] visit = new int[1001][1001] ;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    static int startx=0;
    static int starty=0;
    static int lastx=0;
    static int lasty=0;

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine()," ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(bf.readLine()," ");
            for (int j = 1; j <= m; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        st = new StringTokenizer(bf.readLine()," ");
        h = Integer.parseInt(st.nextToken());
        w = Integer.parseInt(st.nextToken());
        startx = Integer.parseInt(st.nextToken());
        starty = Integer.parseInt(st.nextToken());
        lastx = Integer.parseInt(st.nextToken());
        lasty = Integer.parseInt(st.nextToken());

        if (startx == lastx && starty == lasty)
            System.out.println(0);
        else {
            System.out.println(bfs());
        }

        bf.close();
    }

    static int bfs() {
        Queue<pair> q = new LinkedList<>();
        q.add(new pair(startx,starty));
        visit[startx][starty] = 1;

        while (!q.isEmpty()) {
            pair cur = q.poll();
            if(cur.x == lastx && cur.y ==lasty)
                return visit[cur.x][cur.y]-1;

            for (int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];

                if (visit[nx][ny] == 0) {
                    if (rect(nx, ny))
                        continue;

                    visit[nx][ny] = visit[cur.x][cur.y] + 1;
                    q.add(new pair(nx, ny));
                }
            }
        }
        return -1;
    }

    static boolean rect(int x,int y)
    {
        int cx = x+h-1;
        int cy = y+w-1;
        if(x<1||y<1||cx>n||cy>m)
            return true;

        for(int i=x;i<=cx;i++)
        {
            for(int j=y;j<=cy;j++)
            {
                if(board[i][j]==1)
                    return true;
            }
        }
        return false;
    }
}
class pair
{
    int x;
    int y;
    pair(int x, int y)
    {
        this.x =x;
        this.y = y;
    }
}

rect 함수에서 탈출 조건을 생각을 잘 해야 한다.