463 words
2 minutes
[BOJ] 구슬 탈출 3
TimeLimit | MemoryLimit | Condition | TAG |
---|---|---|---|
2s | 512MB | (3 ≤ N, M ≤ 10) | BFS |
우려먹기 시리즈라 그냥 설명은 첫번째 구슬 탈출 2에서 봐주시면 감사하겠습니다.
정답 코드
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
using ll = long long;
int inf = 1e9+7;
int n ,m;
char board[11][11];
bool visited[11][11][2]; // 0 is red, 1 is blue
pair<pair<int, int>, bool> move(int dx, int dy, int y, int x, pair<int, int> current){
queue<pair<int ,int>> q;
q.push({y, x});
pair<int, int> last;
bool check = false;
while(!q.empty()){
auto [cy, cx] = q.front(); q.pop();
last= {cy, cx};
if(board[cy][cx] == 'O') return {last, false};
if(cy == current.first && cx == current.second) check = true;
int nx = cx + dx;
int ny = cy + dy;
if(0 <= ny && ny < n && 0 <= nx && nx < m && board[ny][nx] != '#') q.push({ny, nx});
}
last.first += dy * -1 * check;
last.second += dx * -1 * check;
return {last, check};
}
pair<int, string> solution(pair<int, int> red_ball, pair<int, int> blue_ball){
queue<pair<pair<int, int>, string>> balls;
int dy[] = {1, -1, 0, 0}, dx[] = {0, 0, 1, -1};
char direction[] = {'D', 'U', 'R', 'L'};
// 근데 뭐가 먼저 움직이는가.. 이게 중요하거든 blue 부터
balls.push({blue_ball, ""});
balls.push({red_ball, ""});
visited[red_ball.first][red_ball.second][0] = true;
visited[blue_ball.first][blue_ball.second][1] = true;
int step = 0;
while(++step <= 10){
int length = balls.size();
while(length > 0){
auto [blue, _] = balls.front(); balls.pop();
auto [red, path] = balls.front(); balls.pop();
for(int i = 0; i < 4; i++){
auto [blue_move, blue_check] = move(dx[i], dy[i], blue.first, blue.second, red);
if(board[blue_move.first][blue_move.second] == 'O') continue;
auto [red_move, red_check] = move(dx[i], dy[i], red.first, red.second, blue);
if(board[red_move.first][red_move.second] == 'O') return {step, path+direction[i]};
balls.push({blue_move, ""});
balls.push({red_move, path + direction[i]});
}
length-=2;
}
//
// cout << "\n";
// for(int i = 0; i < n; i++){
// for(int j = 0; j < m; j++){
// cout << visited[i][j][0] << " ";
// }
// cout << "\n";
// }
// cout << "\n";
}
return {-1, ""};
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
pair<int, int> red_ball, blue_ball, hole;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> board[i][j];
if(board[i][j] == 'B') blue_ball = {i, j};
else if(board[i][j] == 'R') red_ball = {i, j};
else if(board[i][j] == 'O') hole = {i, j};
}
}
// 그렇네.. 허헣 아 그러면
auto [result, path] = solution(red_ball, blue_ball);
cout << result << "\n";
if(result >-1) cout << path;
return 0;
}
[BOJ] 구슬 탈출 3
https://compy07.github.io/Blog/posts/boj/15644/