직사각형 탈출 [백준 16973][JAVA][골드 5][BFS]

 

[광고 누르면 오늘의 행운 상승!!]

https://www.acmicpc.net/problem/16973

16973번: 직사각형 탈출

범위체크 BFS문제

1. 시작점으로부터 BFS를 시작한다.

2. 우선 방문하지않고, 직사각형 넓이가 맵을 벗어나지 않았으면 큐에 넣는다.,

3. 큐에서 꺼낼때 테두리를 검사하여 벽이 있으면 continue한다.

4. 도착지점에 도달하면 거리를 출력한다.

5. 도착지점에 도달하지 못하고 q가 비워졌다면 -1를 리턴한다.

package Study4;

import java.io.*;
import java.util.*;


public class 직사각형탈출 {
	static class Square{
		int row, col, dis;
		public Square(int row, int col, int dis) {
			this.row = row;
			this.col = col;
			this.dis = dis;
		}
	}
	
	static final int[] dx = {-1,0,1,0};
	static final int[] dy = {0,1,0,-1};
	static int[][] map;
	static boolean[][] visit;
	static int N,M,H,W,ans;
	static int Frow,Fcol;
	static Queue<Square> q = new LinkedList<>();
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		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];
		visit = 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());
		int Srow = Integer.parseInt(st.nextToken())-1;
		int Scol = Integer.parseInt(st.nextToken())-1;
		Frow = Integer.parseInt(st.nextToken())-1;
		Fcol = Integer.parseInt(st.nextToken())-1;
		
		q.add(new Square(Srow, Scol, 0));
		visit[Srow][Scol] = true;
		
		System.out.println(bfs());
			
	}
	private static int bfs() {
		
		loop : while(!q.isEmpty()) {
			Square square = q.poll();
			
			for (int i = 0; i < W; i++) {
				if(map[square.row][square.col + i] == 1) continue loop;
				if(map[square.row + H-1][square.col + i] == 1) continue loop;
			}
			
			for (int i = 0; i < H; i++) {
				if(map[square.row +i][square.col+ W-1] == 1) continue loop;
				if(map[square.row +i][square.col] == 1) continue loop;
			}
			if(square.row == Frow && square.col == Fcol) {
				return square.dis;
			}
			
			for (int i = 0; i < 4; i++) {
				int nx = square.row + dx[i];
				int ny = square.col + dy[i];
				
				if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
				else if(nx < 0 || nx >= N || ny+ W-1 < 0 || ny+ W-1 >= M) continue;
				else if(nx+ H-1 < 0 || nx + H-1 >= N || ny < 0 || ny >= M) continue;
				else if(nx + H-1 < 0 || nx + H-1 >= N || ny +W-1 < 0 || ny + W-1 >= M) continue;
				
				if(!visit[nx][ny]) {
					visit[nx][ny] = true;
					q.add(new Square(nx,ny,square.dis + 1));
				}
			}
		}
		return -1;
	}
}