13460 째로탈출 2

13460 째로탈출 2

깔끔한 코드는 도저히 생각이 나지 않아서 경우의 수들에 대해 하드코딩 했다......

가장 중요한 아이디어는 rx, ry, bx, by를 매개변수로 받아 지점에 대한 타당성을 검증하는 것인거 같다. 

1. 직전에 상하로 움직였으면 이번엔 좌우만 움직여보고, 직전에 좌우로 움직였으면 상하로만 움직인다.

2. 파란공을 먼저 움직여보고 타당하면 빨간공을 움직인다.

3. 빨간공까지 움직였을때 빨간공과 파란공의 위치가 같은경우 인자로 받아왔던 rx,ry,bx,by 값을 비교해 둘중 하나를 한칸 옮겨준다.

4. cnt가 10이하인 모든 방법을 탐색한다.

#include <iostream>
#include <algorithm>
#include <string>
#define INF 20
using namespace std;
 
int n, m, rx, ry, bx, by, res;
int map[10][10];
 
void dfs(int rx,int ry,int bx,int by,int dir,int cnt) {
    if (cnt == 11) return;
 
    bool next_flag = false;
 
    int rrx = rx;
    int rry = ry;
    int bbx = bx;
    int bby = by;
 
    //직전칸에서 좌우로 움직인 경우
    if (dir == 1) {
        //위 방향
        for (int i = bbx - 1; i >=0; i--) {
            if (map[i][bby] == 'O') {
                break;
            }
            if (map[i][bby] == '#') {
                bbx = i + 1;
                next_flag = true;
                break;
            }
        }
        if (next_flag) {
            for (int i = rrx - 1; i >= 0; i--) {
                if (map[i][rry] == 'O') {
                    res = min(res, cnt);
                    break;
                }
                if (map[i][rry] == '#') {
                    rrx = i + 1;
                    if (rrx == bbx && ry==by) {
                        if (rx > bx) rrx += 1;
                        else bbx += 1;
                    }
                    dfs(rrx, rry, bbx, bby, 2, cnt + 1);
                    break;
                }
            }
        }
        //아래 방향
        next_flag = false;
        rrx = rx;
        rry = ry;
        bbx = bx;
        bby = by;
        for (int i = bbx + 1; i < n; i++) {
            if (map[i][bby] == 'O') {
                break;
            }
            if (map[i][bby] == '#') {
                bbx = i - 1;
                next_flag = true;
                break;
            }
        }
        if (next_flag) {
            for (int i = rrx + 1; i < n; i++) {
                if (map[i][rry] == 'O') {
                    res = min(res, cnt);
                    break;
                }
                if (map[i][rry] == '#') {
                    rrx = i - 1;
 
                    if (rrx == bbx && ry == by) {
                        if (rx > bx) bbx -= 1;
                        else rrx -= 1;
                    }
                    dfs(rrx, rry, bbx, bby, 2, cnt + 1);
                    break;
                }
            }
        }
 
    }
    //직전칸에서 상하로 움직인 경우
    else if (dir == 2) {
        next_flag = false;
        rrx = rx;
        rry = ry;
        bbx = bx;
        bby = by;
 
        //왼쪽 방향
        for (int i = bby - 1; i >= 0; i--) {
            if (map[bbx][i] == 'O') {
                break;
            }
            if (map[bbx][i] == '#') {
                bby = i + 1;
                next_flag = true;
                break;
            }
        }
        if (next_flag) {
            for (int i = rry - 1; i >= 0; i--) {
                if (map[rrx][i] == 'O') {
                    res = min(res, cnt);
                    break;
                }
                if (map[rrx][i] == '#') {
                    rry = i + 1;
                    if (rx == bx && rry == bby) {
                        if (ry > by) rry += 1;
                        else bby += 1;
                    }
                    dfs(rrx, rry, bbx, bby, 1, cnt + 1);
                    break;
                }
            }
        }
 
        next_flag = false;
        rrx = rx;
        rry = ry;
        bbx = bx;
        bby = by;
 
        //오른쪽 방향
        for (int i = bby + 1; i < m; i++) {
            if (map[bbx][i] == 'O') {
                break;
            }
            if (map[bbx][i] == '#') {
                bby = i - 1;
                next_flag = true;
                break;
            }
        }
        if (next_flag) {
            for (int i = rry + 1; i < m; i++) {
                if (map[rrx][i] == 'O') {
                    res = min(res, cnt);
                    break;
                }
                if (map[rrx][i] == '#') {
                    rry = i - 1;
                    if (rx == bx && rry == bby) {
                        if (ry > by) bby -= 1;
                        else rry -= 1;
                    }
                    dfs(rrx, rry, bbx, bby, 1, cnt + 1);
                    break;
                }
            }
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        string buf;
        cin >> buf;
        for (int j = 0; j < m; j++) {
            map[i][j] = buf[j];
            if (map[i][j] == 'R') {
                rx = i;
                ry = j;
            }
            if (map[i][j] == 'B') {
                bx = i;
                by = j;
            }
        }
    }
 
    res = INF;
    dfs(rx, ry, bx, by, 1, 1);
    dfs(rx, ry, bx, by, 2, 1);
 
    if (res == INF) cout << -1 << endl;
    else cout << res << endl;
    return 0;
}