구슬 집어넣기 게임

철수의 동생이 다니는 학교에서는 ‘구슬 집어넣기 게임’ 선풍적인 인기를 끌고 있다.

 철수 동생은 반 친구들과 이 게임의 성적을 놓고 경쟁을 하고 있다. 어느 날, 철수의 동생이 시무룩한 얼굴을 하고 집에 들어왔다. 친구들보다 좋은 성적을 내지 못했다고 우울했던 것이다. 그래서 철수는 동생을 위해 게임에서 최고 성적을 내는 방법을 알려주는 프로그램을 만들기로 했다. 게임은 다음 룰에 의해 진행된다.

1.게임판에는 빨간구슬, 파란구슬, 벽, 그리고 목표구멍이 있다.

2. 플레이어는 총 10회 게임판을 기울일 수 있다. (방향 : 상하좌우) 

3. 플레이어가 게임판을 기울이게 되면 해당 방향으로 빨간구슬과 파란구슬이 한 칸 이동한다.

4. 이동방향에 벽이 있는 구슬은 움직일 수 없다. 

5. 이동 시 빨간 구슬과 파란 구슬이 같은 위치로 움직여 부딪히는 경우 구슬이 깨지므로, 게임 실패다. 

6. 파란구슬이 목표구멍으로 들어가는 것은 게임 실패다. 

7. 기울임 횟수가 10회를 넘어서면 게임 실패다. 

8. 빨간 구슬이 목표구멍으로 들어가는 것이 이 게임의 목표이다. 

9. 적은 횟수를 기울여 해결할수록 많은 높은 점수를 얻을 수 있다. 

기본적으로 게임판의 가장자리는 구슬이 게임판 밖으로 빠져나가지 못하도록 벽으로 둘러쌓여 있다. 철수는 우선 이 게임에서 문제를 해결할 수 있는 가장 적은 횟수를 알고 싶다. 이를 출력하는 프로그램을 작성하시오. 

#include 
#include 
using namespace std;

const int mapSize = 17;
const int queueSize = 60000;

struct queue {
	int redX;
	int redY;
	int blueX;
	int blueY;
	int count;
};

int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

char map[mapSize][mapSize];
bool visitedRed[mapSize][mapSize];
bool visitedBlue[mapSize][mapSize];

queue myQueue[queueSize];

queue currentData;
queue nextData;

int X;
int Y;

int result;

int wp;
int rp;

bool endFlag = false;

bool isNotEmpty() {
	return wp > rp;
}

void push(queue data) {
	myQueue[wp++] = data;
}

queue pop() {
	return myQueue[rp++];
}

void init() {
	wp = 0;
	rp = 0;
	endFlag = false;
	result = -1;

	for (int i = 0; i < mapSize; i++) {
		for (int j = 0; j < mapSize; j++) {
			visitedBlue[j][i] = false;
			visitedRed[j][i] = false;
		}
	}
}

int main() {
	int testCase;
	cin >> testCase;

	while (testCase--) {
		init();
		result = -1;

		cin >> Y;
		cin >> X;

		for (int i = 0; i < Y; i++) {
			for (int j = 0; j < X; j++) {
				//scanf_s("%c", &map[i][j]);
				cin >> map[i][j];
				if (map[i][j] == 'B') {
					nextData.blueX = j;
					nextData.blueY = i;
				}
				if (map[i][j] == 'R') {
					nextData.redX = j;
					nextData.redY = i;
				}
			}
		}
		// 여기까지 입력 끝

		/*for (int i = 0; i < X; i++) {
			for (int j = 0; j < Y; j++) {
				cout << map[j][i];
			}
			cout << endl;
		}*/

		nextData.count = 0;
		push(nextData);		// 초기 데이터 push
		visitedBlue[nextData.blueY][nextData.blueX] = true;
		visitedRed[nextData.redY][nextData.redX] = true;

		while (isNotEmpty()) {
			if (endFlag == true) break;
			currentData = pop();	// 데이터를 꺼낸다.

			//cout << "red : " << currentData.redY + 1<< " , " << currentData.redX + 1 << endl;
			//cout << "blue : " << currentData.blueY + 1 << " , " << currentData.blueX + 1 << endl;
			//cout << "wp : " << wp << " rp : " << rp << endl;
			//cout << "count : " << currentData.count << endl << endl;			

			if (currentData.count == 10) break;	// 10번의 기회를 모두 소진한 경우
			// 여기서부터는 다음 데이터를 넣는다.
			for (int i = 0; i < 4; i++) {
				if (endFlag == true) break;
				nextData.blueX = currentData.blueX + dx[i];
				nextData.blueY = currentData.blueY + dy[i];
				nextData.redX = currentData.redX + dx[i];
				nextData.redY = currentData.redY + dy[i];

				// 방문검사
				if ((visitedRed[nextData.redY][nextData.redX] == true) &&
					(visitedBlue[nextData.blueY][nextData.blueX] == true)) {
					//cout << "갈 수 없어" << endl;
					continue;
				}

				// 둘다 벽이라서 기울여도 같은 위치라면 움직일 필요가 없음.
				if ((map[nextData.blueY][nextData.blueX] == '#') && (map[nextData.redY][nextData.redX] == '#')) continue;

				if (map[nextData.blueY][nextData.blueX] == '#') {	// 벽을 만나면 이동불가
					nextData.blueY -= dy[i];
					nextData.blueX -= dx[i];
				}
				if (map[nextData.redY][nextData.redX] == '#') {		// 벽을 만나면 이동불가
					nextData.redY -= dy[i];
					nextData.redX -= dx[i];
				}

				// 종료조건 및 조건검사
				if (map[nextData.redY][nextData.redX] == 'H') {	// 빨간 공이 구멍에 들어가면 성공
					//cout << "빨간공이 들어갔다." << endl;
					result = currentData.count + 1;
					endFlag = true;
					break;
				}

				if (map[nextData.blueY][nextData.blueX] == 'H') {	// 파란 공이 구멍에 들어가면 실패
					//cout << "파란공이 들어갔다." << endl;
					continue;
				}

				if ((nextData.blueX == nextData.redX) && (nextData.blueY == nextData.redY)) {
					//cout << "공이 부딪혔다." << endl;
					continue;
				}

				//cout << "red : " << nextData.redY + 1 << " , " << nextData.redX + 1 << "로 갑니다." << endl;
				//cout << "blue : " << nextData.blueY + 1 << " , " << nextData.blueX + 1 << "로 갑니다." << endl << endl;

				nextData.count = currentData.count + 1;
				push(nextData);
				visitedBlue[nextData.blueY][nextData.blueX] = true;
				visitedRed[nextData.redY][nextData.redX] = true;
			}
		}
		cout << result << endl;
	}
	//system("pause");
}