[BOJ] 백준 13460 구슬 탈출 2

[문제]

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

 

 

[소스 코드]

import java.io.*;
import java.util.*;
public class Main {
	static class Marble{
		int rr,rc,br,bc,cnt;
		Marble(int rr,int rc,int br,int bc,int cnt){
			this.rr = rr;
			this.rc = rc;
			this.br = br;
			this.bc = bc;
			this.cnt = cnt;
		}
	}
	static char[][] map;
	static boolean[][][][] visit;
	static int redR,redC,blueR,blueC;
	static int[] dr = {-1,1,0,0};
	static int[] dc = {0,0,-1,1};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		map = new char[n][m];
		
		for(int i=0;i<n;i++) {
			String s = br.readLine();
			for(int j=0;j<m;j++) {
				map[i][j] = s.charAt(j);
				if(map[i][j]=='R') {
					redR = i;
					redC = j;
				}
				if(map[i][j]=='B') {
					blueR = i;
					blueC = j;
				}
			}
		}
		visit = new boolean[n][m][n][m];
		System.out.println(move());
	}
	private static int move() {
		Queue<Marble> q = new LinkedList<>();
		visit[redR][redC][blueR][blueC] = true;
		q.offer(new Marble(redR,redC,blueR,blueC,1));
		while(!q.isEmpty()) {
			Marble curr = q.poll();
			
			for(int d=0;d<4;d++) {
				boolean goalR = false;
				boolean goalB = false;
				int newRr = curr.rr;
				int newRc = curr.rc;
				int newBr = curr.br;
				int newBc = curr.bc;
				int currCnt = curr.cnt;
				
				while(map[newRr+dr[d]][newRc+dc[d]]!='#') {
					newRr += dr[d];
					newRc += dc[d];
					if(map[newRr][newRc]=='O') {
						goalR = true;
						break;
					}
				}
				while(map[newBr+dr[d]][newBc+dc[d]]!='#') {
					newBr += dr[d];
					newBc += dc[d];
					if(map[newBr][newBc]=='O') {
						goalB = true;
						break;
					}
				}
				if(goalB) continue;
				if(goalR && !goalB) {
					return currCnt;
				}
				if(newRr==newBr && newRc==newBc) {
					if(d==0) {
						if(curr.rr>curr.br) {
							newRr -= dr[d];
						}
						else {
							newBr -= dr[d];
						}
					}
					else if(d==1) {
						if(curr.rr>curr.br) {
							newBr -= dr[d];
						}
						else {
							newRr -= dr[d];
						}
					}
					else if(d==2) {
						if(curr.rc>curr.bc) {
							newRc -= dc[d];
						}
						else {
							newBc -= dc[d];
						}
					}
					else {
						if(curr.rc>curr.bc) {
							newBc -= dc[d];
						}
						else {
							newRc -= dc[d];
						}
					}
				}
				if(currCnt>10) {
					return -1;
				}
				if(!visit[newRr][newRc][newBr][newBc]) {
					visit[newRr][newRc][newBr][newBc] = true;
					q.offer(new Marble(newRr,newRc,newBr,newBc,currCnt + 1));
				}
			}
		}
		return -1;
	}
}