[백준/자바] 16973 직사각형 탈출

 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

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

예제 입력 2

6 7
0 0 0 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 1
0 0 1 0 0 0 0
0 0 0 0 0 0 0
2 3 1 1 5 5

예제 출력 2

8

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

---

코드

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.LinkedList;
	import java.util.Queue;
	import java.util.StringTokenizer;
	public class BOJ16973 {
	static int map[][];
	static int n;
	static int m;
	static int h;
	static int w;
	static coordinate[] move = {new coordinate(-1, 0), new coordinate(1, 0), new coordinate(0, 1), new coordinate(0, -1)};
	static coordinate start;
	static coordinate end;
	static boolean visited[][];
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	n = Integer.parseInt(st.nextToken());
	m = Integer.parseInt(st.nextToken());
	map = 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++) {
	map[i][j] = Integer.parseInt(st.nextToken());
	}
	}
	st = new StringTokenizer(br.readLine());
	h = Integer.parseInt(st.nextToken());
	w = Integer.parseInt(st.nextToken());
	start = new coordinate(Integer.parseInt(st.nextToken())-1, Integer.parseInt(st.nextToken())-1);
	end = new coordinate(Integer.parseInt(st.nextToken())-1, Integer.parseInt(st.nextToken())-1);
	System.out.println(bfs());
	}
	static int bfs() {
	Queue<rectangle> q = new LinkedList<>();
	q.offer(new rectangle(start.x, start.y, 0));
	visited[start.x][start.y] = true;
	while(!q.isEmpty()) {
	rectangle cur = q.poll();
	if(cur.x == end.x && cur.y == end.y) {
	return cur.count;
	}
	for(int i = 0; i < 4; i++) {
	int x = cur.x + move[i].x;
	int y = cur.y + move[i].y;
	boolean check = true;
	if(x < 0 || n <= x || y < 0 || m <= y || n < x+h || m < y+w) {
	continue;
	}
	if(visited[x][y]) {
	continue;
	}
	for(int a = x; a < h+x; a++) {
	for(int b = y; b < w+y; b++) {
	if(map[a][b] == 1) {
	check = false;
	break;
	}
	}
	if(!check) {
	break;
	}
	}
	if(check) {
	visited[x][y] = true;
	q.offer(new rectangle(x, y, cur.count+1));
	}
	}
	}
	return -1;
	}
	static class rectangle {
	int x;
	int y;
	int count;
	rectangle(int x, int y, int count) {
	this.x = x;
	this.y = y;
	this.count = count;
	}
	}
	static class coordinate {
	int x;
	int y;
	coordinate(int x, int y) {
	this.x = x;
	this.y = y;
	}
	}
	}

view raw BOJ16973.java hosted with ❤ by GitHub