백준 13460 구슬탈출2 C++

문제

www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

 

코드

#include<bits/stdc++.h>

using namespace std;

struct Ball
{
	int redY, redX, blueY, blueX, count;
};

Ball ball;
int n, m, answer = 987654321, visited[10][10][10][10], dy[] = { -1, 0, 1, 0 }, dx[] = { 0, 1, 0, -1 };
char board[10][10];
queue<Ball> q;

void input()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> board[i][j];
			if (board[i][j] == 'R')
			{
				ball.redY = i;
				ball.redX = j;
			}

			if (board[i][j] == 'B')
			{
				ball.blueY = i;
				ball.blueX = j;
			}
		}
	}
}

void run(int& y, int& x, int dir)
{
	while (true)
	{
		//공이 굴러갈 수 있는 조건은
		//벽이 아니고, 구멍이 아닐 때 이다.
		if (board[y][x] != '#' && board[y][x] != 'O')
		{
			y += dy[dir];
			x += dx[dir];
		}
		else
		{
			if (board[y][x] == '#')
			{
				y -= dy[dir];
				x -= dx[dir];
			}
			break;
		}
	}
}

void go()
{
	ball.count = 0;
	q.push(ball);
	visited[ball.redY][ball.redX][ball.blueY][ball.blueX] = 1;
	while (q.size())
	{
		Ball curBall = q.front();
		q.pop();

		//10회가 넘어갈경우 더 이상 공을 굴리지 않아도 된다.
		if (curBall.count > 10)
		{
			continue;
		}

		//파란구슬이 구멍에 빠지면 실패라고 문제에 나와있지만, -1을 출력하라는 조건은 없기때문에
		//break 가 아니라 continue를 해준다.
		if (board[curBall.redY][curBall.redX] != 'O' && board[curBall.blueY][curBall.blueX] == 'O')
		{
			continue;
		}

		//빨강공만 구멍에 잘 도착했다.
		if (board[curBall.redY][curBall.redX] == 'O' && board[curBall.blueY][curBall.blueX] != 'O')
		{
			answer = min(answer, curBall.count);
			continue;
		}

		for (int i = 0; i < 4; i++)
		{
			int nextRedY = curBall.redY;
			int nextRedX = curBall.redX;
			int nextBlueY = curBall.blueY;
			int nextBlueX = curBall.blueX;

			//빨강공을 굴리자
			run(nextRedY, nextRedX, i);
			//파랑공을 굴리자
			run(nextBlueY, nextBlueX, i);
			
			//빨강공과 파랑공을 굴렸으니 파랑공과 빨강공의 위치를 체크하자.
			//빨강공과 파랑공의 위치가 같을 경우
			if (nextRedY == nextBlueY && nextRedX == nextBlueX)
			{
				if (board[nextRedY][nextRedX] != 'O')
				{
					int redBallDis = abs(curBall.redY - nextRedY) + abs(curBall.redX - nextRedX);
					int blueBallDis = abs(curBall.blueY - nextBlueY) + abs(curBall.blueX - nextBlueX);
					if (redBallDis > blueBallDis)
					{
						nextRedY -= dy[i];
						nextRedX -= dx[i];
					}
					else
					{
						nextBlueY -= dy[i];
						nextBlueX -= dx[i];
					}
				}
				else
				{
					continue;
				}
			}
			if (visited[nextRedY][nextRedX][nextBlueY][nextBlueX] == 0)
			{
				visited[nextRedY][nextRedX][nextBlueY][nextBlueX] = 1;
				Ball nextBall;
				nextBall.redY = nextRedY;
				nextBall.redX = nextRedX;
				nextBall.blueY = nextBlueY;
				nextBall.blueX = nextBlueX;
				nextBall.count = curBall.count + 1;
				q.push(nextBall);
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	input();
	go();

	answer = ((answer == 987654321) ? -1 : answer);
	cout << answer << "\n";

	return 0;
}