백준 13460 구슬 탈출 2

- bfs 최대 장점 사용 - visit 를 4차원으로 활용 - 구슬의 경우의 수를 어떻게 할 것인지 확실하게 하기. - 조건에 대해서 철저하게 하기. - 처음과 끝의 경우가 있습니다. 가운데의 경우에만 맞추는 것이 아니라 처음부터 맞추기 위해서 꼼꼼히 짜야 합니다. - 큐의 한 덩어리를 돌리기 위해서 2가지 방법이 있는데, 2번째 것이 더욱 안정적입니다. 아래서 ++ 를 하고 그 위에서 종료 조건을 제시하도록 합니다. while(qlen--) 밖에서 종료조건, ++ 을 순서대로 작성합니다.

/*
1320 구슬 탈출 2 풀이하기
몇번 안에 뺄 수 있는지 확인하기
10번을 넘어가면 아웃.

bfs 로 돌립니다.
visit 는 4차원으로 사용해서 빨간, 파란구슬의 위치를 저장합니다.

*/
 
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
#define SIZE 21
char map[SIZE][SIZE];
int ans;
struct point {
    int rx, ry, bx, by, cnt;
};
queue<point> que;
int N, M;
int rx, ry, bx, by, cnt;
int visit[11][11][11][11];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int nrx, nry, nbx, nby;
int orx, ory, obx, oby;
 
void problemIn() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> map[i];
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 'B') {
                bx = i;
                by = j;
                map[i][j] = '.';
            }
            else if (map[i][j] == 'R') {
                rx = i;
                ry = j;
                map[i][j] = '.';
            }
        }
    }
}
 
void init() {
 
}
 
/*
1. 홀에 들어가는 경우,
2. 홀에 안들어가는 경우,
3. 겹치는 경우
*/
void bfs() {
 
 
    while (!que.empty()) {
        orx = que.front().rx;
        ory = que.front().ry;
        obx = que.front().bx;
        oby = que.front().by;
        cnt = que.front().cnt;
        que.pop();
 
        if (cnt >= 11) {
            ans = -1;
            return;
        }
 
        if (map[orx][ory] == 'O' && map[obx][oby] != 'O') {
            ans = cnt;
            return;
        }
 
        for (int i = 0; i < 4; i++) {
            rx = orx, ry = ory, bx = obx, by = oby;
            // 빨간 구술의 이동.
            while (map[rx + dx[i]][ry + dy[i]] != '#' && map[rx][ry] != 'O') {
                rx += dx[i];
                ry += dy[i];
            }
 
            while (map[bx + dx[i]][by + dy[i]] != '#' && map[bx][by] != 'O') {
                bx += dx[i];
                by += dy[i];
            }
 
            if (rx == bx && ry == by) {
                if (map[bx][by] == 'O') continue;
                if (abs(rx - orx) + abs(ry - ory) > abs(bx - obx) + abs(by - oby)) {
                    rx -= dx[i];
                    ry -= dy[i];
                }
                else {
                    bx -= dx[i];
                    by -= dy[i];
                }
 
            }
 
            if (visit[rx][ry][bx][by] == 0) {
                visit[rx][ry][bx][by] = 1;
                que.push({ rx,ry,bx,by,cnt + 1 });
            }
        }
    }
 
    ans = -1;
    return;
}
 
void solve() {
 
    que.push({ rx,ry,bx,by,0 });
    visit[rx][ry][bx][by] = 1;
    bfs();
 
}
 
int main() {
    problemIn();
    solve();
    //    if (ans == 0) ans = -1;
    cout << ans << endl;
    return 0;
}