[PS] BOJ 13460 구슬 탈출 2

실제로 판을 기울였을 때 구슬의 상태를 구하는 함수 4가지(left,right,top,bottom)을 구현하고

큐를 이용해서 BFS를 수행한다. 중복된 경우의 수는 제거하고, 파란공이 어찌됬던간에 들어가면 게임 오버다. 다만 빨간공이 나중에 들어갈 가능성이 있으니까 파란공이 들어갔다고 게임을 끝내면 안된다.

#include<iostream>
#include<sstream>
#include<vector>
#include<limits>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
using namespace std;
using Board = vector<vector<char>>;
Board bloom;
int N, M;
void print(Board& board) {
    cout << endl;
    for (int y = 0; y < N; y++) {
        for (int x = 0; x < M; x++) {
            cout << board[y][x];
        }
        cout << endl;
    }
}
Board left(Board board, char& gameover) {
    for (int y = 0; y < N; y++) {
        for (int x = 0; x < M; x++) {
            if (board[y][x] == 'R' || board[y][x] == 'B') {
                int cx = x;
                while (cx != 1) {
                    if (board[y][cx - 1] == 'O') {
                        gameover = board[y][cx];
                        board[y][cx] = '.';
                    }
                    if (board[y][cx-1] == '.')
                        swap(board[y][cx], board[y][cx - 1]);
                    else
                        break;
                    cx--;
                }
            }
        }
    }
    return board;
}
Board right(Board board,char& gameover) {
    for (int y = 0; y < N; y++) {
        for (int x = M-1; x >=0; x--) {
            if (board[y][x] == 'R' || board[y][x] == 'B') {
                int cx = x;
                while (cx != M-2) {
                    if (board[y][cx + 1] == 'O') {
                        gameover = board[y][cx];
                        board[y][cx] = '.';
                    }
                    if (board[y][cx+1] == '.')
                        swap(board[y][cx], board[y][cx + 1]);
                    else
                        break;
                    cx++;
                }
            }
        }
    }
    return board;
}
Board top(Board board, char& gameover) {
    for (int y = 0; y < N; y++) {
        for (int x = 0; x < M; x++) {
            if (board[y][x] == 'R' || board[y][x] == 'B') {
                int cy = y;
                while (cy != 1) {
                    if (board[cy - 1][x] == 'O') {
                        gameover = board[cy][x];
                        board[cy][x] = '.';
                    }
                    if (board[cy - 1][x] == '.')
                        swap(board[cy][x], board[cy - 1][x]);
                    else
                        break;
                    cy--;
                }
            }
        }
    }
    return board;
}
Board bottom(Board board, char& gameover) {
    for (int y = N-1; y >=0; y--) {
        for (int x = 0; x < M; x++) {
            if (board[y][x] == 'R' || board[y][x] == 'B') {
                int cy = y;
                while (cy != N - 2) {
                    if (board[cy + 1][x] == 'O') {
                        gameover = board[cy][x];
                        board[cy][x] = '.';
                    }
                    if (board[cy + 1][x] == '.')
                        swap(board[cy][x], board[cy + 1][x]);
                    else
                        break;
                    cy++;
                }
            }
        }
    }
    return board;
}
int location(Board& board,char c) {
    for (int y = 0; y < N; y++) {
        for (int x = 0; x < M; x++) {
            if (board[y][x] == c) {
                return y * M + x;
            }
        }
    }
    return 0;
}
using Func=Board(*)(Board, char&);
int bfs(Board board) {
    queue<pair<Board,int>> stk;
    stk.push(make_pair(board,0));
    set<int> bloom;
    bloom.insert(location(board, 'R') * 9999 + location(board, 'B'));
    Func func[4] = { top,left,right,bottom };
    while (stk.empty() == false) {
        Board stk_board= stk.front().first;
        int move = stk.front().second;
        stk.pop();
       
        for (int i = 0; i < 4; i++) {
            char over = '.';
            Board res_board = func[i](stk_board, over);
            if (over == 'R' && location(res_board, 'B')!=0)return move + 1;
            if (over != 'B') {
                int locval = location(res_board, 'R') * 9999 + location(res_board, 'B');
                if (bloom.find(locval) == bloom.end()) {
                    bloom.insert(locval);
                    stk.push(make_pair(res_board, move + 1));
                }
            }
        }
    }
    return -1;
}
int main() {
    cin >> N >> M;
    Board board(N, vector<char>(M));
    bloom.assign(N, vector<char>(M,0));
    for (int y = 0; y < N; y++) {
        for (int x = 0; x < M; x++) {
            cin >> board[y][x];
        }
    }
    int A = bfs(board);
    cout <<((A>10)?-1:A) << endl;
    return 0;
}