son3933   3년 전

#include

#include

#include

using namespace std;

struct bead

{

int rx, ry, bx, by, count;

};

int bfs(bead init, char board[][11])

{

board[init.rx][init.ry] = '.';

board[init.bx][init.by] = '.';

queue q;

q.push(init);

int dx[4] = { 0, 1, 0, -1 };

int dy[4] = { -1, 0, 1, 0 };

int visited[10][10][10][10] = { 0, };

visited[init.rx][init.ry][init.bx][init.by] = 1;

int ret = -1;

while (!q.empty()) {

bead cur = q.front();

q.pop();

if (cur.count > 10) {

break;

}

for (int dir = 0; dir < 4; dir++) {

bead next = cur;

int countr = 0;

int countb = 0;

int fail = 1;

int success = 0;

while (board[next.bx + dx[dir]][next.by + dy[dir]] != '#') {

if (board[next.bx + dx[dir]][next.by + dy[dir]] == 'O') {

fail = 0;

next.bx = cur.bx;

next.by = cur.by;

break;

}

next.bx = next.bx + dx[dir];

next.by = next.by + dy[dir];

countb++;

}

while (board[next.rx + dx[dir]][next.ry + dy[dir]] != '#' && fail) {

if (board[next.rx + dx[dir]][next.ry + dy[dir]] == 'O') {

return cur.count + 1;

}

next.rx = next.rx + dx[dir];

next.ry = next.ry + dy[dir];

countr++;

}

if (next.rx == next.bx && next.ry == next.by && fail) {

if (countr > countb) {

next.rx = next.rx - dx[dir];

next.ry = next.ry - dy[dir];

}

else {

next.bx = next.bx - dx[dir];

next.by = next.by - dy[dir];

}

}

next.count = cur.count + 1;

if (visited[next.rx][next.ry][next.bx][next.by] == 0) {

visited[next.rx][next.ry][next.bx][next.by] = 1;

q.push(next);

}

}

}

return -1;

}

int main(int argc, char** argv)

{

int row, col;

cin >> row >> col;

char board[10][11];

bead game = { 0, };

for (int i = 0; i < row; i++)

{

for (int j = 0; j < col; j++)

{

cin >> board[i][j];

if (board[i][j] == 'R') {

game.rx = i;

game.ry = j;

}

if (board[i][j] == 'B') {

game.bx = i;

game.by = j;

}

}

}

int ans = bfs(game, board);

cout << ans << endl;

return 0;

}

댓글을 작성하려면 로그인해야 합니다.