368 words
2 minutes
[BOJ] 구슬 탈출 4
TimeLimit | MemoryLimit | Condition | TAG |
---|---|---|---|
2s | 512MB | (3 ≤ N, M ≤ 10) | BFS |
우려먹기 그 마지막 시리즈
정답 코드
#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][11][11]; // 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};
}
int solution(pair<int, int> red_ball, pair<int, int> blue_ball){
queue<pair<int, int>> balls;
int dy[] = {1, -1, 0, 0}, dx[] = {0, 0, 1, -1};
// 근데 뭐가 먼저 움직이는가.. 이게 중요하거든 blue 부터
balls.push(blue_ball);
balls.push(red_ball);
visited[red_ball.first][red_ball.second][blue_ball.first][blue_ball.second] = true;
int step = 1;
while(!balls.empty()){
int length = balls.size()/2;
while(length --> 0){
pair<int, int> blue = balls.front(); balls.pop();
pair<int, int> red = 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;
if(visited[red_move.first][red_move.second][blue_move.first][blue_move.second])
continue;
visited[red_move.first][red_move.second][blue_move.first][blue_move.second] = true;
balls.push(blue_move);
balls.push(red_move);
}
}
step++;
}
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};
}
}
// 그렇네.. 허헣 아 그러면
cout << solution(red_ball, blue_ball);
return 0;
}
[BOJ] 구슬 탈출 4
https://compy07.github.io/Blog/posts/boj/15653/