13460번 - 구슬 탈출 2
#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;
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;
댓글을 작성하려면 로그인해야 합니다.
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;
}