글 읽기 - 왜 틀렸는지 모르겠어요ㅜㅜ

qkrtmdrkr1 5년 전 0

대회 테스트케이스를 다운받아서 돌려본 결과

2번째 테스트케이스에 대해서만 틀린 답(IMPOSSIBLE)이 나옵니다.

해당 테스트케이스의 사이즈( w, h)가 너무 커서 디버깅을 하고 싶은데 쉽지가 않네요 ㅠㅠ

소스코드의 어느부분때문에 틀렸는지 잘 모르겠습니다...

찾아주시면 감사하겠습니다!

#include <stdio.h>

struct node
{
	int x;
	int y;
	char c;
};
char mat[1002][1002];
int len[1002][1002];
struct node que[1005000];

int tail = -1;
int head = -1;
int testcase;
int w, h;

void init(void)
{
	head = -1;
	tail = -1;

	for (int i = 0; i < 1002; i++)
	{
		for (int j = 0; j < 1002; j++)
		{
			len[i][j] = 0;
			mat[i][j] = 0;

		}
	}

	for (int i = 0; i < 1005000; i++)
	{
		que[i].x = 0;
		que[i].y = 0;
		que[i].c = 0;
	}
}

void escape(int temp_x, int temp_y)
{
	tail++;
	que[tail].x = temp_x;
	que[tail].y = temp_y;
	que[tail].c = '@';

	while (head != tail)
	{
		int temp_x;
		int temp_y;
		char c;

		head++;

		temp_x = que[head].x;
		temp_y = que[head].y;
		c = que[head].c;


		//// Fire

		if (c == '*')
		{
            // '.'이거나 '@'일 경우에만 불 번지도록
			// Left
			if (temp_y - 1 >= 0 && mat[temp_x][temp_y - 1] != '#' && mat[temp_x][temp_y - 1] != '*')
			{
				tail++;

				que[tail].x = temp_x;
				que[tail].y = temp_y - 1;
				que[tail].c = '*';
				mat[temp_x][temp_y - 1] = '*';
			}

			// Up
			if (temp_x - 1 >= 0 && mat[temp_x - 1][temp_y] != '#' && mat[temp_x - 1][temp_y] != '*')
			{
				tail++;

				que[tail].x = temp_x - 1;
				que[tail].y = temp_y;
				que[tail].c = '*';
				mat[temp_x - 1][temp_y] = '*';
			}

			// Right
			if (temp_y + 1 < w && mat[temp_x][temp_y + 1] != '#' && mat[temp_x][temp_y + 1] != '*')
			{
				tail++;

				que[tail].x = temp_x;
				que[tail].y = temp_y + 1;
				que[tail].c = '*';
				mat[temp_x][temp_y + 1] = '*';
			}

			// Down
			if (temp_x + 1 < h && mat[temp_x + 1][temp_y] != '#' && mat[temp_x + 1][temp_y] != '*')
			{
				tail++;

				que[tail].x = temp_x + 1;
				que[tail].y = temp_y;
				que[tail].c = '*';
				mat[temp_x + 1][temp_y] = '*';
			}

		}
		//// Human

		if (c == '@')
		{
			if (temp_x == 0 || temp_y == 0 || temp_x == h - 1 || temp_y == w - 1)
			{
				printf("%d\n", len[temp_x][temp_y] + 1);
				return;
			}
			// Left
			if (temp_y - 1 >= 0 && mat[temp_x][temp_y - 1] == '.')
			{
				tail++;

				que[tail].x = temp_x;
				que[tail].y = temp_y - 1;
				que[tail].c = '@';
				mat[temp_x][temp_y - 1] = '@';
				len[temp_x][temp_y - 1] = len[temp_x][temp_y] + 1;

				if (temp_y - 1 == 0)
				{
					printf("%d\n", len[temp_x][temp_y - 1] + 1);
					return;
				}
			}

			// Up
			if (temp_x - 1 >= 0 && mat[temp_x - 1][temp_y] == '.')
			{
				tail++;

				que[tail].x = temp_x - 1;
				que[tail].y = temp_y;
				que[tail].c = '@';
				mat[temp_x - 1][temp_y] = '@';
				len[temp_x - 1][temp_y] = len[temp_x][temp_y] + 1;

				if (temp_x - 1 == 0)
				{
					printf("%d\n", len[temp_x - 1][temp_y] + 1);
					return;
				}
			}


			// Right
			if (temp_y + 1 < w && mat[temp_x][temp_y + 1] == '.')
			{
				tail++;

				que[tail].x = temp_x;
				que[tail].y = temp_y + 1;
				que[tail].c = '@';
				mat[temp_x][temp_y + 1] = '@';
				len[temp_x][temp_y + 1] = len[temp_x][temp_y] + 1;

				if (temp_y + 1 == w - 1)
				{
					printf("%d\n", len[temp_x][temp_y + 1] + 1);
					return;
				}
			}


			// Down
			if (temp_x + 1 < w && mat[temp_x + 1][temp_y] == '.')
			{
				tail++;

				que[tail].x = temp_x + 1;
				que[tail].y = temp_y;
				que[tail].c = '@';
				mat[temp_x + 1][temp_y] = '@';
				len[temp_x + 1][temp_y] = len[temp_x][temp_y] + 1;

				if (temp_x + 1 == h - 1)
				{
					printf("%d\n", len[temp_x + 1][temp_y] + 1);
					return;
				}
			}

		}
	}

	printf("IMPOSSIBLE\n");
	return;
}


int main(void)
{
	int temp_x, temp_y;

	scanf("%d", &testcase);

	for (int i = 0; i < testcase; i++)
	{
		init();
		scanf("%d %d",&w, &h);

		for (int j = 0; j < h; j++)
		{
			scanf("%s",mat[j]);

			for (int k = 0; k < w; k++)
			{
				if (mat[j][k] == '@')
				{
					temp_x = j;
					temp_y = k;
				}
				else if (mat[j][k] == '*')
				{
					tail++;
					que[tail].x = j;
					que[tail].y = k;
					que[tail].c = '*';
				}
			}
		}

		escape(temp_x, temp_y);
		
	}


	return 0;
}

djm03178 5년 전 1

이 코드와 같이 모든 방향에 대한 처리를 전부 별개의 코드에서 하면 지금과 같은 실수를 할 위험이 큽니다. 177번째 줄은 w가 아니라 h여야 합니다.

그래서 4방향 탐색의 경우 int dy[] = {0, 0, 1, -1}, dx[] = {1, -1, 0, 0} 과 같이 각 방향을 배열에 저장해두고, 반복문을 돌려서 처리해주는 것이 코드도 간결하고 응집성이 높아져 실수할 위험이 적습니다.

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

문제

문제

출처

ICPC

왜 틀렸는지 모르겠어요ㅜㅜ

qkrtmdrkr1 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말