[bfs] 백준 13460 구슬 탈출2

https://www.acmicpc.net/problem/13460

파란색이랑 빨간색 동시에 움직이게 하는 거에 막혀서...

솔직히 이번 문제는 다른 분의 블로그를 보고 풀었습니다.

#include <iostream>
#include <cmath>
#include <queue>
using namespace std;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
bool visited[10][10][10][10];
char map[10][10];
queue<pair<pair<int,int>,pair<int,int>>> q;
int bfs();
 
int main(){
    int n,m;
    int bx,by,rx,ry;
    
    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] == 'R') {rx = j; ry = i;}
            else if(map[i][j] == 'B'){bx = j; by = i;}
        }
    }
    q.push({{rx,ry},{bx,by}});
    visited[rx][ry][bx][by] = 1;
    
    cout << bfs();
}
 
int bfs(){
    int cnt = 0;
    
    while(!q.empty()){
        int size = q.size();
        for(int i = 0; i < size; i++){
            int rx = q.front().first.first;
            int ry = q.front().first.second;
            int bx = q.front().second.first;
            int by = q.front().second.second;
            q.pop();
            
            if(map[ry][rx] == 'O' && map[by][bx] != map[ry][rx]) return cnt;
            for(int j = 0; j < 4; j++){
                int rxt = rx, ryt = ry, bxt = bx, byt = by;
                while(map[ryt+dy[j]][rxt+dx[j]] != '#' && map[ryt][rxt] != 'O'){    
                    rxt += dx[j]; ryt += dy[j];
                }
                while(map[byt+dy[j]][bxt+dx[j]] != '#' && map[byt][bxt] != 'O'){
                    bxt += dx[j]; byt +=dy[j];
                }
                if(bxt == rxt && byt == ryt){
                    if(map[ryt][rxt] =='O') continue;
                    if(abs(rxt-rx)+abs(ryt-ry) > abs(byt-by)+abs(bxt-bx)){
                        ryt-=dy[j]; rxt-=dx[j];
                    }
                    else{
                        bxt-=dx[j]; byt-=dy[j];
                    }
                }
                if(visited[rxt][ryt][bxt][byt])continue;
                q.push({{rxt,ryt},{bxt,byt}});
                visited[rxt][ryt][bxt][byt]=1;
            }
            
        }
        if(cnt == 10) return -1;
        cnt ++;
    }
    return -1;
}