[백준]구슬탈출2(두번째)

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

13460번: 구슬 탈출 2

 

역시나 어려운 문제... 최단거리 --> bfs,   상화좌우로 이동 --> 시뮬로 쭉 끝까지 이동 

isV를 4차원으로 생각 , 여러가지 예외상황과 겹치는 경우 많이 이동한 구슬이 전단계로 Back.. 등등

 

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
struct INFO {
    int rr, rc, br, bc;
    INFO() {};
    INFO(int rr, int rc, int br, int bc) :rr(rr), rc(rc), br(br), bc(bc) {};
};
 
int N, M;
char map[10][10];
bool isV[10][10][10][10]; //R_r,R_c,B_r,B_c
int Red_r, Red_c, Blue_r, Blue_c;
int R, C;
int dr[] = { 1,-1,0,0 }, dc[] = { 0,0,1,-1 };
int ans = 1e9;
queue<INFO> q;
 
void move(int &r, int &c, int dir) {
    while (1) {
        r += dr[dir];
        c += dc[dir];
        if (map[r][c] == '#') { r -= dr[dir]; c -= dc[dir]; break; }
        if (map[r][c] == 'O') break;
    }
}
 
void solve() {
    int cnt = 1;
    while (!q.empty()) {
        int qlen = q.size();
        while (qlen--) { //사이즈만큼 실행 --> 단계별로 실행.
            int nrr = q.front().rr, nrc = q.front().rc;
            int nbr = q.front().br, nbc = q.front().bc;
            q.pop();
 
            for (int i = 0; i < 4; i++) {
                int nr = nrr, nc = nrc, nr1 = nbr, nc1 = nbc;
                move(nr, nc, i);
                move(nr1, nc1, i);
                
                if (map[nr1][nc1] == 'O') continue; //파란구슬이 빠지는 경우
                if (map[nr][nc] == 'O') { ans = cnt; return; } //빨간구슬만 빠지는 경우
                if (nr == nr1 && nc == nc1) { //겹치는 경우
                    if (abs(nr - nrr) + abs(nc - nrc) < abs(nr1 - nbr) + abs(nc1 - nbc)) nr1 -= dr[i], nc1 -= dc[i];
                    else nr -= dr[i], nc -= dc[i];
                }
                if (isV[nr][nc][nr1][nc1] == true) continue;
                isV[nr][nc][nr1][nc1] = true;
                q.push({ nr,nc,nr1,nc1 });
            }
        }
        //queue end
        if (cnt >= 10) return;
        cnt++;
    }
}
 
int main()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
            if (map[i][j] == 'R') { Red_r = i; Red_c = j; }
            else if (map[i][j] == 'B') { Blue_r = i; Blue_c = j; }
            else if (map[i][j] == 'O') { R = i; C = j; }
        }
    }
    //queue 시작.
    q.push({ Red_r,Red_c,Blue_r,Blue_c });
    isV[Red_r][Red_c][Blue_r][Blue_c] = true;
    solve();
 
    printf("%d\n", ans == 1e9 ? -1 : ans);
    return 0;
}