BFS 를 공부하기 위한 아주 기본적이고 좋은 문제이다.
#include<bits/stdc++.h>
using namespace std;
int N,M;
int red_ball_y,red_ball_x,blue_ball_y,blue_ball_x;
char Map[11][11];
int answer = 11;
int dir[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };//동,서,남,북
void input(){
cin>>N>>M;
for(int i=0;i<N;i++)for(int j=0;j<M;j++){
cin>>Map[i][j];
if(Map[i][j] == 'B'){
blue_ball_y = i;
blue_ball_x = j;
Map[i][j] = '.';
}
else if(Map[i][j] == 'R'){
red_ball_y = i;
red_ball_x = j;
Map[i][j] = '.';
}
}
}
void bfs(int count,int cur_dir,int red_y,int red_x,int blue_y,int blue_x){
if(count > 10 || count >= answer){
return;
}
//move ball
//방향에 따른 먼저 움직일 공 찾기
int first_move = 0;//0 = red first, 1 = bluefirst
int red_finish = 0,blue_finish = 0;
if(cur_dir==0){//동쪽
if(red_y==blue_y){
if(blue_x>red_x){//blue first
first_move = 1;
}
else{//red first
first_move = 0;
}
}
}
else if(cur_dir==1){//서쪽
if(red_y==blue_y){
if(blue_x>red_x){//red first
first_move = 0;
}
else{//blue first
first_move = 1;
}
}
}
else if(cur_dir==2){//남쪽
if(red_x==blue_x){
if(blue_y>red_y){//blue first
first_move = 1;
}
else{//red first
first_move = 0;
}
}
}
else if(cur_dir==3){//북쪽
if(red_x==blue_x){
if(blue_y>red_y){//red first
first_move = 0;
}
else{//red first
first_move = 1;
}
}
}
if(first_move == 0){//red, blue
//red
while(Map[red_y][red_x]=='.' ){ //.이 아닐때까지 이동
red_y += dir[cur_dir][0];
red_x += dir[cur_dir][1];
}
if(Map[red_y][red_x]=='O'){//O를 만나면 체크
red_finish=1;
}
else if(Map[red_y][red_x]=='#'){//벽을 만나면 1칸 이동 취소
red_y-=dir[cur_dir][0];
red_x-=dir[cur_dir][1];
Map[red_y][red_x] = 'R';
}
//blue
while(Map[blue_y][blue_x]=='.'){
blue_y += dir[cur_dir][0];
blue_x += dir[cur_dir][1];
}
if(Map[blue_y][blue_x]=='O'){
blue_finish=1;
}
else if( Map[blue_y][blue_x] == 'R' || Map[blue_y][blue_x] == '#'){
blue_y -= dir[cur_dir][0];
blue_x -= dir[cur_dir][1];
}
if(Map[red_y][red_x]!='O') Map[red_y][red_x] = '.';
}
else{//blue, red
//blue
while(Map[blue_y][blue_x]=='.' ){
blue_y += dir[cur_dir][0];
blue_x += dir[cur_dir][1];
}
if(Map[blue_y][blue_x]=='O'){
blue_finish=1;
}
else if(Map[blue_y][blue_x]=='#'){
blue_y -= dir[cur_dir][0];
blue_x -= dir[cur_dir][1];
Map[blue_y][blue_x] = 'B';
}
//red
while(Map[red_y][red_x]=='.' ){
red_y += dir[cur_dir][0];
red_x += dir[cur_dir][1];
}
if(Map[red_y][red_x]=='O'){
red_finish=1;
}
else if( Map[red_y][red_x]=='B' || Map[red_y][red_x] == '#'){
red_y-=dir[cur_dir][0];
red_x-=dir[cur_dir][1];
}
if(Map[blue_y][blue_x]!='O') Map[blue_y][blue_x] = '.';
}
if(red_finish == 1 && blue_finish == 1){
return;
}
else if(red_finish == 1 && blue_finish ==0){
answer = count;
return;
}
else if(red_finish==0 && blue_finish==1){
return;
}
//next move
for(int i=0;i<4;i++){
if(i != cur_dir){
bfs(count+1,i,red_y,red_x,blue_y,blue_x);
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
input();
//각각 첫번째 이동이 동,서,남,북인 경우를 모두 계산
bfs(1,0,red_ball_y,red_ball_x,blue_ball_y,blue_ball_x);
bfs(1,1,red_ball_y,red_ball_x,blue_ball_y,blue_ball_x);
bfs(1,2,red_ball_y,red_ball_x,blue_ball_y,blue_ball_x);
bfs(1,3,red_ball_y,red_ball_x,blue_ball_y,blue_ball_x);
//10 이하인 답을 찾지 못 한 경우
if(answer == 11)cout<<"-1\n";
else cout<<answer<<"\n";
}