글 읽기 - 실패하는 테스트 케이스 부탁 드립니다.

furylion 5년 전 0

안녕하세요?

하기와 같이 코드를 작성하였는데, 질문 게시판에 있는 테스트 케이스는 모두 통과하는 것으로 확인됩니다.

혹시 실패하는 테스트 케이스를 알려주시면 감사하겠습니다.

그럼 즐거운 하루 되세요.

감사합니다.

#pragma warning (disable:4996)

#include <stdio.h>

typedef struct _POS
{
	int x;
	int y;
	int type; /* '-': 0 , '|': 1 */
}POS;

int N;
char map[50][50];
int visit[50][50][2];
int result;

char buf[256];

typedef struct _QUEUE
{
	POS pos;
	int depth;
}QUEUE;

QUEUE queue[2500];

POS B, E;

int dx[5] = { 0, 0, 1, -1, 0}; /* E W S N R */
int dy[5] = { 1, -1, 0, 0, 0};

void bfs()
{
	int i;
	int front, rear;
	int x[3], y[3], t;
	POS pos;
	int depth;
	front = 0;
	rear = 0;

	queue[rear].pos.x = B.x;
	queue[rear].pos.y = B.y;
	queue[rear].pos.type = B.type;
	queue[rear++].depth = 0;

	while (front != rear)
	{
		pos.x = queue[front].pos.x;
		pos.y = queue[front].pos.y;
		pos.type = queue[front].pos.type;
		depth = queue[front++].depth;

		if (pos.x == E.x && pos.y == E.y && pos.type == E.type)
		{
			result = depth;
			return;
		}

		for (i = 0; i < 5; i++)
		{
			x[1] = pos.x + dx[i];
			y[1] = pos.y + dy[i];
			t = pos.type;

			if (t == 0) /* '-' */
			{
				x[0] = x[1];
				y[0] = y[1] - 1;
				x[2] = x[1];
				y[2] = y[1] + 1;
			}
			else       /* '|' */
			{
				x[0] = x[1] - 1;
				y[0] = y[1];
				x[2] = x[1] + 1;
				y[2] = y[1];
			}

			if (i == 4)
			{
				t = (t == 0) ? 1 : 0;

				if (t == 0) /* '-' */
				{
					x[0] = x[1];
					y[0] = y[1] - 1;
					x[2] = x[1];
					y[2] = y[1] + 1;
				}
				else       /* '|' */
				{
					x[0] = x[1] - 1;
					y[0] = y[1];
					x[2] = x[1] + 1;
					y[2] = y[1];
				}

				if (x[0] >= 0 && y[0] >= 0 && x[2] < N && y[2] < N && map[x[0]][y[0]] != '1' && map[x[1]][y[1]] != '1' && map[x[2]][y[2]] != '1' && visit[x[1]][y[1]][t] == 0)
				{
					if (map[x[1] - 1][y[1] - 1] != '1' && map[x[1] - 1][y[1] + 1] != '1' && map[x[1] + 1][y[1] - 1] != '1' && map[x[1] + 1][y[1] + 1] != '1')
					{
						visit[x[1]][y[1]][t] = 1;
						queue[rear].pos.x = x[1];
						queue[rear].pos.y = y[1];
						queue[rear].pos.type = t;
						queue[rear++].depth = depth + 1;
					}
				}
			}
			else
			{
				if (x[0] >= 0 && y[0] >= 0 && x[2] < N && y[2] < N && map[x[0]][y[0]] != '1' && map[x[1]][y[1]] != '1' && map[x[2]][y[2]] != '1' && visit[x[1]][y[1]][t] == 0)
				{
					visit[x[1]][y[1]][t] = 1;
					queue[rear].pos.x = x[1];
					queue[rear].pos.y = y[1];
					queue[rear].pos.type = t;
					queue[rear++].depth = depth + 1;
				}
			}
		}
	}

}

int main(void)
{
	int i, j, k;
	int Bx[3];
	int By[3];
	int Ex[3];
	int Ey[3];
	int cntB, cntE;

	scanf("%d", &N);

	if (N < 4 || N > 50)
	{
		printf("0\n");
		return 0;
	}

	cntB = 0;
	cntE = 0;
	result = 0;

	for (i = 0; i < N; i++)
	{
		scanf("%s", &map[i]);
		for (j = 0; j < N; j++)
		{
			if (map[i][j] == 'B')
			{
				Bx[cntB] = i;
				By[cntB++] = j;
			}
			else if (map[i][j] == 'E')
			{
				Ex[cntE] = i;
				Ey[cntE++] = j;
			}
		}
	}

	/* Set B log */
	B.x = Bx[1];
	B.y = By[1];
	if (Bx[0] == Bx[1])
	{
		B.type = 0;
	}
	else
	{
		B.type = 1;
	}

	/* Set E log */
	E.x = Ex[1];
	E.y = Ey[1];
	if (Ex[0] == Ex[1])
	{
		E.type = 0;
	}
	else
	{
		E.type = 1;
	}

	for (i = 0; i < N; i++)
		for (j = 0; j < N; j++)
			for (k = 0; k < 2; k++)
				visit[i][j][k] = 0;

	visit[Bx[1]][By[1]][B.type] = 1;
	bfs();

	printf("%d", result);

	return 0;
}

djm03178 5년 전 0

첫째로, 한 변의 길이가 최대 50이기 때문에 %s로 입력을 받는다면 매 줄은 최소 51칸이 필요합니다. 문자열의 끝에는 널 문자가 삽입되기 때문입니다.

그리고 큐의 크기가 너무 작습니다. 50*50칸에 가로/세로 상태까지 저장해야 하므로 최소 5000칸이 필요합니다.

furylion 5년 전 0

답변 대단히 감사합니다. 큐 크기에서 가로세로를 고려 못했네요. 그럼 즐거운 하루 되세요~~

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

문제

문제

출처

ICPC

실패하는 테스트 케이스 부탁 드립니다.

furylion 5년 전 0

djm03178 5년 전 0

furylion 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말