글 읽기 - 13460문제 반례 여러가지 찾아서 돌려봤는데 틀립니다.

shincchh 5년 전 0

반례 하나만 들어주세요 ㅠㅠㅠ

도저히 못찾겠어요..

#include <stdio.h>
#include <queue>
using namespace std;

#define SIZE 15

struct DAT
{
	int dir;
	int dx;
	int dy;
	int count;
};

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

queue<DAT> qR;
queue<DAT> qB;

char map[SIZE][SIZE];

int gdx, gdy;
int width, height;

int Bfs()
{
	int result = 0;
	int queueCount = -1;

	while (true)
	{
		if(qR.size() == 0)
			return -1;

		int dxR = qR.front().dx;
		int dyR = qR.front().dy;
		int cR = qR.front().count;
		int dR = qR.front().dir;
		int dxB = qB.front().dx;
		int dyB = qB.front().dy;
		int cB = qB.front().count;
		int dB = qB.front().dir;

		queueCount = (cR < cB) ? cR : cB;

		bool qCheckR = false;
		bool qCheckB = false;

		if (queueCount == cR)
		{
			qCheckR = true;
			qR.pop();
			//printf("%d pop  %d %d\n", queueCount, dxR, dyR);
		}
		if (queueCount == cB)
		{
			qCheckB = true;
			qB.pop();
			//printf("            %d pop  %d %d\n", queueCount, dxB, dyB);
		}

		for (int i = 0; i < 4; i++)
		{
			int tempXR = dx[i];
			int tempYR = dy[i];
			int tempXB = dx[i];
			int tempYB = dy[i];

			bool blueCheck = false;
			int countR = 0;
			int countB = 0;
			
			bool nextR = false;
			bool nextB = false;
			bool oneMore = false;

			while (nextR == false || nextB == false || oneMore == false)
			{
				if (nextR == true && nextB == true) oneMore = true;

				if ((qCheckR == true &&
					map[dyR + tempYR][dxR + tempXR] == '.') &&
					((dxB + tempXB != dxR + tempXR + dx[i]) || (dyB + tempYB != dyR + tempYR + dy[i])))
				{
					countR++;
					tempXR += dx[i];
					tempYR += dy[i];
				}
				else nextR = true;

				if ((qCheckB == true &&
					map[dyB + tempYB][dxB + tempXB] == '.') &&
					((dxB + tempXB + dx[i] != dxR + tempXR) || (dyB + tempYB + dy[i] != dyR + tempYR)))
				{
					countB++;
					tempXB += dx[i];
					tempYB += dy[i];
				}
				else nextB = true;
			}

			if (qCheckB == false) {}
			else if (map[dyB + tempYB][dxB + tempXB] == 'O')
			{
				blueCheck = true;
			}
			else
			{
				if ((countB != 0 || countR != 0))
				{
					if (map[dyB + tempYB + +dy[i]][dxB + tempXB + +dx[i]] == 'O')
						continue;

					qB.push({ i, dxB + tempXB - dx[i], dyB + tempYB - dy[i], cB + 1 });
					//printf("              push %d %d\n", dxB + tempXB - dx[i], dyB + tempYB - dy[i]);
				}
			}

			if (qCheckR == false) {}
			if (map[dyR + tempYR][dxR + tempXR] == 'O')
			{
				if (map[dyB + tempYB + +dy[i]][dxB + tempXB + +dx[i]] == 'O')
					continue;

				result = cR + 1;
				return result;
			}
			else
			{
				if (blueCheck == true) 
					continue;
					
				if ((countB != 0 || countR != 0))
				{
					qR.push({i, dxR + tempXR - dx[i], dyR + tempYR - dy[i], cR + 1 });
					//printf("  push %d %d\n", dxR + tempXR - dx[i], dyR + tempYR - dy[i]);
				}	
			}

			if (queueCount >= 10) 
				return -1;
		}
	}

	return -1;
};

void Input()
{
	scanf_s("%d %d ",  &height, &width);

	for (int i = 0; i < height; i++)
	{
		for (int j = 0; j < width + 1; j++)
		{
			scanf_s("%c", &map[i][j]);

			if (map[i][j] == 'O')
			{
				gdx = i;
				gdy = j;
			}
			else if(map[i][j] == 'R')
			{
				qR.push({ -1, j, i, 0});
				map[i][j] = '.';
			}
			else if (map[i][j] == 'B')
			{
				qB.push({ -1, j, i, 0 });
				map[i][j] = '.';
			}
		}
	}
}; 

int main()
{
	int result = 0;
	 
	Input();

	result = Bfs();

	printf("%d", result);
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

13460문제 반례 여러가지 찾아서 돌려봤는데 틀립니다.

shincchh 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말