13460.cpp - 구슬 탈출 2

#include <iostream>
#include <queue>
using namespace std;

struct step
{
	int ry, rx; //빨간공
	int by, bx; //파란공
	int cnt; //카운트 
};

//graph, visited 준비
char graph[11][11];
bool visited[11][11][11][11];
// n, m 준비
int n, m;
// dy, dx 준비
int dy[4] = {1,-1,0,0};
int dx[4] = {0,0,1,-1};

// move: graph 내 #이나 O를 만날 때까지 이동
void move(int& ny, int& nx, int& distance, int& i)
{
	while (graph[ny+dy[i]][nx+dx[i]]!='#' && graph[ny][nx]!='O')
	{
		ny += dy[i];
		nx += dx[i];
        distance+=1;
	}
}

// bfs: Breadth First Search
int bfs(int ry, int rx, int by, int bx)
{
    // queue 준비 (struct로)
	queue<step> q;
    // cnt 준비
	int cnt = 0;
    // q에 첫번째 넣기
	q.push({ry, rx, by, bx, cnt});
    // 첫번째 방문처리
	visited[ry][rx][by][bx] = true;
    
    // q가 빌 때까지
	while (!q.empty())
	{
        // 맨 앞으로, 변수 초기화
		ry = q.front().ry;
		rx = q.front().rx;
		by = q.front().by;
		bx = q.front().bx;
		cnt = q.front().cnt;
        // 앞 빼내기
		q.pop();
		
        // cnt가 10이 넘었으면 탈출
		if (cnt>=10) break;
		
        // 4방향 move 진행
		for (int i = 0; i<4; i++)
		{
            // 변수 초기화
			int nry = ry, nrx = rx, nby = by, nbx = bx;
			int rd = 0, bd = 0, ncnt = cnt+1;
			
            // moving~
			move(nry, nrx, rd, i);
			move(nby, nbx, bd, i);
			
            // 파란공이 구멍에 => 스킾
			if (graph[nby][nbx]=='O') continue;
            // 빨간공이 구멍에 => 정답
			if (graph[nry][nrx]=='O') return ncnt;
			
            // 파란공과 빨간공 같은 위치에
			if (nry == nby && nrx == nbx)
			{
                // red distance > blue distance
				if (rd>bd) nry-=dy[i], nrx-=dx[i];
                // red distance < blue distance
				else nby-=dy[i], nbx-=dx[i];
			}
            // 방문했다면 => 스킾
			if (visited[nry][nrx][nby][nbx]) continue;
            // 아니라면 방문처리
			visited[nry][nrx][nby][nbx] = true;
            // 그리고 q에 넣어~
			q.push({nry, nrx, nby, nbx, ncnt});
			
		}
	}
    // 정답이 없다면
	return -1;
}

void solution()
{
	cin>>n>>m;
	int ry, rx, by, bx;
	for (int y = 0; y<n ; y++)
	{
		for (int x = 0; x<m ; x++)
		{
			cin>>graph[y][x];
			if (graph[y][x]=='R') ry = y, rx = x;
			if (graph[y][x]=='B') by = y, bx = x;
		}
	}
	cout<<bfs(ry, rx, by, bx);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	solution();
	return 0;
}