[백준] 13460번 구슬 탈출 2 (gold 1

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

class Node {
    char color;
    int x;
    int y;
    public Node(char color, int x, int y){
        this.color=color;
        this.x=x;
        this.y=y;
    }
}
public class Main{
    static int n;
    static int m;
    static char[][] map;
    static Node red;
    static Node blue;
    //홀에 들어가면 +1, 파란공이면 -1을해서. 1일경우가 정상 종료. 외에는 불가.
    static int exit =0;
    //홀에 들어간 경우, 하나라도 들어가면 true
    static boolean useHole=false;
    static int min=Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st=new StringTokenizer(br.readLine());
        n=Integer.valueOf(st.nextToken());
        m=Integer.valueOf(st.nextToken());

        map=new char[n+1][m+1];
        //맵 생성하기.
        for(int i=1; i<=n; i++){
            String a=br.readLine();
            for(int j=1; j<=m; j++) {
                char temp = a.charAt(j - 1);
                if (temp == 'R') {
                    red = new Node('R',j, i);
                    map[i][j]='R';
                }
                else if (temp == 'B') {
                    blue = new Node('B',j, i);
                    map[i][j]='B';
                }
                else {
                    map[i][j] = a.charAt(j - 1);
                }
            }
        }


        back(1);
        bw.write(min==Integer.MAX_VALUE ? "-1" : min+"");
        bw.flush();

    }

    public static void back(int n){
        if(n==11 || n>=min){
            return;
        }
        Node tR=new Node(red.color, red.x, red.y);
        Node tB=new Node(blue.color, blue.x, blue.y);

        //파란공과 빨간공이 같은 라인으로 움직일 때, 
        //방향의 앞쪽에 있는 공부터 움직여야됨. 
        //뒤의 공부터 움직이려면 중간에 막혀서 못감.
        for(int i=1; i<=4; i++){
            if(i==1){
                if(red.y<blue.y){
                    up(red);
                    up(blue);
                }
                else{
                    up(blue);
                    up(red);
                }
            }
            else if(i==2){
                if(red.y>blue.y){
                    down(red);
                    down(blue);
                }
                else{
                    down(blue);
                    down(red);
                }
            }
            else if(i==3){
                if(red.x<blue.x){
                    right(blue);
                    right(red);
                }
                else{
                    right(red);
                    right(blue);
                }
            }
            else{
                if(red.x>blue.x){
                    left(blue);
                    left(red);
                }
                else{
                    left(red);
                    left(blue);
                }
            }

            //공이 하나라도 홀에 들어간 경우
            if(useHole){
                //만약 1이면 빨간공만 들어간거,
                //파랑만 들어가면 -1, 
                //홀에 들어간 공이 있는데, 0이면 두공다 들어간 거이므로 패스.
                //빨간공만 들어간 경우 최소값 비교.
                if(exit==1){
                    min= min > n ? n : min;
                }
                exit=0;
                useHole=false;
                goBack(red,tR,blue,tB);
            }

            back(n+1);
            goBack(red,tR,blue,tB);
        }
    }

    //이동하기.
    public static void up(Node p){
        for(int i=p.y; i>1; i--){
            if(possible(p.x, i-1)){
                if(hole(p.x,i-1,p.color)) {
                    remove(p);
                    return;
                }
            }
            else{
                change(p.x,p.y, p.x, i, p);
                return;
            }
        }
    }

    public static void down(Node p){
        for(int i=p.y; i<n; i++){
            if(possible(p.x, i+1)){
                if(hole(p.x,i+1,p.color)){
                    remove(p);
                    return;
                }
            }
            else{
                change(p.x,p.y, p.x, i, p);
                return;
            }
        }
    }
    public static void right(Node p){
        for(int i=p.x; i<m; i++){
            if(possible(i+1, p.y)){
                if(hole(i+1,p.y, p.color)) {
                    remove(p);
                    return;
                }
            }
            else{
                change(p.x,p.y, i, p.y, p);
                return;
            }
        }
    }
    public static void left(Node p){
        for(int i=p.x; i>1; i--){
            if(possible(i-1, p.y)){
                if(hole(i-1,p.y, p.color)) {
                    remove(p);
                    return;
                }
            }
            else{
                change(p.x,p.y, i, p.y, p);
                return;
            }
        }
    }
    //더 못가는 경우는 false, 가능하면 true출력
    public static boolean possible(int x,int y){
        if(map[y][x]=='R' || map[y][x]=='B' || map[y][x]=='#'){
            return false;
        }
        return true;
    }
    //구멍일 경우 구멍에 들어간 경우이므로, 색깔이 어떠하든, useHole은 true;
    //공 색에 따라서, exit에 수를 더하거나 뺀다.
    public static boolean hole(int x, int y, char color){
        if(map[y][x]=='O'){
            useHole=true;
            if(color=='R'){
                exit++;
            }
            else if(color=='B'){
                exit--;
            }
            return true;
        }
        return false;
    }
    //구멍에 빠진 경우. 구멍에 빠진 공은 맵에서 지우기.
    public static void remove(Node p){
        if(p.color=='R'){
            map[red.y][red.x]='.';
        }
        else if(p.color=='B'){
            map[blue.y][blue.x]='.';
        }
    }
    //맵 이동사항 저장.
    public static void change(int x, int y, int tx, int ty, Node p){
        map[y][x]='.';
        map[ty][tx]=p.color;
        p.x=tx;
        p.y=ty;
    }
    //백 트래킹 중간에 구슬의 위치를 다시 돌리기.
    public static void goBack(Node red, Node tempR, Node blue, Node tempB){
        map[red.y][red.x]='.';
        map[blue.y][blue.x]='.';
        red.x=tempR.x;
        red.y=tempR.y;
        blue.x=tempB.x;
        blue.y=tempB.y;
        map[red.y][red.x]='R';
        map[blue.y][blue.x]='B';
    }
}