글 읽기 - 36%에서 막히는데... 반례 찾아주시면 감사하겠습니다..

sujae03 6년 전 0

ㅠㅠ 36%에서 막히네요..
어떤 테스트케이스에서 잘못 됬을까요 ??
#define _CRT_SECURE_NO_WARNINGS
#define MAX 11
#include <stdio.h>
#include <queue>
#include <stdlib.h>

using namespace std;
queue <int> r_x;
queue <int> r_y;
queue <int> b_x;
queue <int> b_y;
int X, Y;
char map[MAX][MAX];
int res;
int cnt;
int SuccesChk;
int IsFail;
void __Input()
{
	scanf("%d %d", &X, &Y);
	getchar();            // '\n'
	for (int i = 0; i < X; i++)
	{
		for (int j = 0; j < Y; j++)
		{
			scanf("%c", &map[i][j]);
			if (map[i][j] == 'R') {  r_x.push(i); r_y.push(j); }
			else if (map[i][j] == 'B') { b_x.push(i); b_y.push(j); }
		}
		getchar();
	}
}

int __RangeChk(int i, int rx, int ry, int bx, int by)
{
	if (i == 0)
	{
		//Up
		if (map[rx - 1][ry] == '.' || map[rx - 1][ry] == 'O' || map[bx - 1][by] == '.') { return 1; }
	}
	else if (i == 1)
	{
		//Right
		if (map[rx][ry + 1] == '.'  || map[rx][ry + 1] == 'O' || map[bx][by + 1] == '.')  { return 1; }
	}
	else if (i == 2)
	{
		//Down
		if (map[rx+1][ry] == '.'  || map[rx + 1][ry] == 'O' || map[bx + 1][by] == '.') { return 1; }
	}
	else if (i == 3)
	{
		//Left
		if (map[rx][ry - 1] == '.'  || map[rx][ry - 1] == 'O' || map[bx][by - 1] == '.'  ) { return 1; }
	}

	return 0;
}

void __Prt(int rx, int ry, int bx, int by)
{
	for (int i = 0; i < X; i++) {
		for (int j = 0; j < Y; j++) {
			printf("%c",map[i][j]);
		}
		printf("\n");
	}
	printf("\n");
	map[rx][ry] = '.';
	map[bx][by] = '.';
}
void __Up(int rx, int ry, int bx, int by)
{
	//__Prt();
	while (1)
	{
		if (!__RangeChk(0, rx, ry, bx, by)) { break; }
		
		if (map[rx - 1][ry] == '.')
		{
			map[rx][ry] = '.';
			rx = rx - 1;
			map[rx][ry] = 'R';
		}
		else if (map[rx - 1][ry] == 'O')
		{
			while (1)
			{
				if (map[bx-1][by] == '.')
				{
					bx = bx - 1;
				}
				else if (map[bx-2][by] == 'O')
				{
					break;
				}
				else
				{
					SuccesChk = 1;
					break;
				}
			}
			if (SuccesChk)
			{
				break;
			}
		}

		if (map[bx - 1][by] == '.')
		{
			map[bx][by] = '.';
			bx = bx - 1;
			map[bx][by] = 'B';
		}
		else if (map[bx - 1][by] == 'O'|| (map[rx-1][ry ] == 'O'&&map[bx - 2][by] == 'O'))
		{
			SuccesChk = 0;
			IsFail = 0;
			break;
		}
	}
	if (IsFail)
	{
		IsFail = 0;
		map[rx][ry] = '.';
		map[bx][by] = '.';
	}
	else {
		//__Prt();
		map[rx][ry] = '.';
		map[bx][by] = '.';
		cnt++;
		r_x.push(rx);
		r_y.push(ry);
		b_x.push(bx);
		b_y.push(by);
	}
}
void __Right(int rx, int ry, int bx, int by)
{
	//__Prt();
	while (1)
	{
		if (!__RangeChk(1, rx, ry, bx, by)) { break; }

		if (map[rx][ry+1] == '.')
		{
			map[rx][ry] = '.';
			ry = ry + 1;
			map[rx][ry] = 'R';
		}
		else if (map[rx][ry+1] == 'O')
		{
			while (1)
			{
				if (map[bx][by +1] == '.')
				{
					by = by + 1;
				}
				else if (map[bx][by + 2] == 'O')
				{
					break;
				}
				else
				{
					SuccesChk = 1;
					break;
				}
			}
			if (SuccesChk)
			{
				break;
			}
		}

		if (map[bx][by+1] == '.')
		{
			map[bx][by] = '.';
			by = by + 1;
			map[bx][by] = 'B';
		}
		else if (map[bx][by+1] == 'O'|| (map[rx][ry + 1] == 'O'&&map[bx][by+2]=='O'))
		{
			SuccesChk = 0;
			IsFail = 1;
			break;
		}
	}
	if (IsFail)
	{
		IsFail = 0;
		map[rx][ry] = '.';
		map[bx][by] = '.';
	}
	else {
		//__Prt();
		map[rx][ry] = '.';
		map[bx][by] = '.';
		cnt++;
		r_x.push(rx);
		r_y.push(ry);
		b_x.push(bx);
		b_y.push(by);
	}
}
void __Down(int rx, int ry, int bx, int by)
{
	//__Prt();
	while (1)
	{
		if (!__RangeChk(2, rx, ry, bx, by)) { break; }

		if (map[rx + 1][ry] == '.')
		{
			map[rx][ry] = '.';
			rx = rx + 1;
			map[rx][ry] = 'R';
		}
		else if (map[rx + 1][ry] == 'O')
		{
			
			while (1)
			{
				if (map[bx+1][by ] == '.')
				{
					bx = bx +1;
				}
				else if (map[bx+2][by] == 'O')
				{
					break;
				}
				else
				{
					SuccesChk = 1;
					break;
				}
			}
			if (SuccesChk)
			{
				break;
			}
		}

		if (map[bx + 1][by] == '.')
		{
			map[bx][by] = '.';
			bx = bx + 1;
			map[bx][by] = 'B';
		}
		else if (map[bx + 1][by] == 'O'|| (map[rx+1][ry] == 'O'&&map[bx + 2][by] == 'O'))
		{
			SuccesChk = 0;
			IsFail = 1;
			break;
		}
	}
	if (IsFail)
	{
		IsFail = 0;
		map[rx][ry] = '.';
		map[bx][by] = '.';
	}
	else {
		//__Prt();
		map[rx][ry] = '.';
		map[bx][by] = '.';
		cnt++;
		r_x.push(rx);
		r_y.push(ry);
		b_x.push(bx);
		b_y.push(by);
	}
}
void __Left(int rx, int ry, int bx, int by)
{
	//__Prt();
	while (1)
	{
		if (!__RangeChk(3, rx, ry, bx, by)) { break; }

		if (map[rx][ry - 1] == '.')
		{
			map[rx][ry] = '.';
			ry = ry - 1;
			map[rx][ry] = 'R';
		}
		else if (map[rx][ry - 1] == 'O')
		{
			while (1)
			{
				if (map[bx][by - 1] == '.')
				{
					by = by - 1;
				}
				else if (map[bx][by - 2] == 'O')
				{
					break;
				}
				else
				{
					SuccesChk = 1;
					break;
				}
			}
		}
		if (SuccesChk)
		{
			break;
		}
		if (map[bx][by - 1] == '.')
		{
			map[bx][by] = '.';
			by = by - 1;
			map[bx][by] = 'B';
		}
		else if (map[bx][by - 1] == 'O'|| (map[rx][ry-1]=='O'&&map[bx][by - 2] == 'O'))
		{
			SuccesChk = 0;
			IsFail = 1;
			break;
		}
	}
	if (IsFail)
	{
		IsFail = 0;
		map[rx][ry] = '.';
		map[bx][by] = '.';
	}
	else {
		//__Prt();
		map[rx][ry] = '.';
		map[bx][by] = '.';
		cnt++;
		r_x.push(rx);
		r_y.push(ry);
		b_x.push(bx);
		b_y.push(by);
	}
}
void __BFS(int rx, int ry, int bx, int by)
{
	
	while (1)
	{	
		if (cnt == r_x.size())
		{
			res++;
			cnt = 0;
		}
		if (res > 9) { printf("-1\n"); break; }
		if (!r_x.empty()) {
			rx = r_x.front(); ry = r_y.front();
		}
		if (!b_x.empty())
		{
			bx = b_x.front(); by = b_y.front();
		}
		for (int i = 0; i < 4; i++)
		{
			map[rx][ry] = 'R';
			map[bx][by] = 'B';
			if (!__RangeChk(i, rx, ry, bx, by)) { ; }
			else
			{
				if (i == 0) { __Up(rx, ry, bx, by); }
				else if (i == 1) { __Right(rx, ry, bx, by); }
				else if (i == 2) { __Down(rx, ry, bx, by); }
				else if (i == 3) { __Left(rx, ry, bx, by); }
			}
			map[rx][ry] = '.';
			map[bx][by] = '.';
		}
		if (SuccesChk) { printf("%d\n", res+1); break; }
		if (!r_x.empty()) {
			r_x.pop();
			r_y.pop();
		}
		if (!b_x.empty())
		{
			b_x.pop();
			b_y.pop();
		}
	}

}

int main(void) {

	freopen("in.txt", "r", stdin);
	__Input();
	if (r_x.empty() || b_x.empty()) { printf("-1\n"); return 0; }
	__BFS(r_x.front(), r_y.front(), b_x.front(), b_y.front());

	return 0;
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

36%에서 막히는데... 반례 찾아주시면 감사하겠습니다..

sujae03 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
