백준 13460 구슬 탈출 2

1. 큐가 먼저 끝나는 경우도 있음. 2. 10이되기 전에 끝나는 경우에도 처리를 해주어야 합니다. 3. cnt 와 종료조건에 대해서 명확하게 합니다. 4. 시간에 관해서 ++ 와 종료조건에 대해서 명확하게 합니다. 5. 10번이하이므로 10번까지 가능합니다. 10번 돌렸는데, 정답을 못찾으면 리턴합니다.

/*
13460 구슬 탈출 2

21:17 시작
21:46
29분컷

설계 과정
1. 문제를 정확하게 읽습니다.
2. 설계를 완벽하게 합니다. (예제 3개 돌리기)
3. 경우의 수를 나열합니다.
4. 초기화 관련 변수를 확인합니다.
5. 가지치기를 합니다.
5. 예제와 동일한 변수 선언 및 사용합니다.

풀이 과정
1. bfs 를 사용하여, 빨간 구슬과 파란 구슬의 위치를 저장합니다.
2. 이중 와일문을 사용하여, 덩어리째 처리합니다.
3. 세세한 조건을 정확하게 입력합니다.

*/
 
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define SIZE 12
int N, M;
char map[SIZE][SIZE];
struct point {
    int rx, ry, bx, by;
};
queue<point> que;
int cnt;
int rx, ry, bx, by;
int nrx, nry, nbx, nby;
int orx, ory, obx, oby;
int ans;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int visit[SIZE][SIZE][SIZE][SIZE];
 
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] == 'R') {
                rx = i;
                ry = j;
                map[i][j] = '.';
            }
            else if (map[i][j] == 'B') {
                bx = i;
                by = j;
                map[i][j] = '.';
            }
        }
    }
}
 
void init() {
 
}
 
void bfs() {
 
    while (!que.empty()) {
        int qlen = que.size();
        while (qlen--) {
            orx = que.front().rx;
            ory = que.front().ry;
            obx = que.front().bx;
            oby = que.front().by;
            que.pop();
 
            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 (1) {
                    nrx = rx + dx[i];
                    nry = ry + dy[i];
                    if (map[nrx][nry] == '#' || map[rx][ry] == 'O') break;
                    rx = nrx;
                    ry = nry;
                }
 
                //파란구슬 이동
                while (1) {
                    nbx = bx + dx[i];
                    nby = by + dy[i];
                    if (map[nbx][nby] == '#' || map[bx][by] == 'O') break;
                    bx = nbx;
                    by = nby;
                }
 
                if (rx == bx && ry == by) {
                    if (map[bx][by] == 'O') continue;
                    if (abs(orx - rx) + abs(ory - ry) > abs(obx - bx) + abs(oby - by)) {
                        rx -= dx[i];
                        ry -= dy[i];
                    }
                    else {
                        bx -= dx[i];
                        by -= dy[i];
                    }
                }
 
                if (visit[rx][ry][bx][by]) continue;
                visit[rx][ry][bx][by] = 1;
                que.push({ rx,ry,bx,by });
            }
        }
        if (cnt == 10) {
            ans = -1;
            return;
        }
        cnt++;
    }
 
    ans = -1; // 큐가 먼저 끝나는 경우.
    return;
}
 
void solve() {
 
    visit[rx][ry][bx][by] = 1;
    que.push({ rx,ry,bx,by });
    bfs();
 
}
 
int main() {
    problemIn();
    solve();
    cout << ans << endl;
}