글 읽기 - 비버의 집이 1숲의 가장자리, 2바위, 3물 로 둘러쌓여 있으면 조기 종료한다..

20170620 6년 전 0

제목과 같이

비버의 숲이 물이나 바위 혹은 맵의 가장자리로 둘러쌓여 있으면 더 이상 진행이 무의미하니 KAKTUS 하고 조기 종료하는 함수를 설계했습니다.

bool checkFail(void);

해당 함수 없이 진행하면 맞는데.. 집어넣으니 60%에서 틀리네요

통찰력 있으신 한 수 부탁드립니다.

#include <stdio.h>
#include <queue>
#include <string.h>

using namespace std;

int moveparam[4][2] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, {0,-1} };
int w, h;
int map[50][50];
int checked[50][50];
int Sy, Sx;
int Dy, Dx;

typedef struct point{
	int y, x, type;
	point(int inY, int inX, int inType)
	{
		y = inY;
		x = inX;
		type = inType;
	}
} point;

// 문제의 함수
bool checkFail(void)
{
	int isblocked = 0;
	for (int dir = 0; dir < 4; dir++)
	{
		int nextY = Dy + moveparam[dir][0];
		int nextX = Dx + moveparam[dir][1];

		if (nextY == -1 || nextX == -1 || nextY == h || nextX == w || map[nextY][nextX] == 'X' || map[nextY][nextX] == '*')
			// 스킵
			isblocked++;
	}
	
	if (isblocked == 4)
		return true;
	else
		return false;
}

int main(void)
{
	queue<point> que;

	scanf_s("%d %d", &h, &w);
	getchar(); // enter
	for (int y = 0; y < h; y++){
		for (int x = 0; x < w; x++){
			scanf_s("%1c", &map[y][x]);
			
			// 물을 큐에
			if (map[y][x] == '*')
				que.push(point(y, x, 1)); // 물:type1
			// 고슴도치 위치 체크
			else if (map[y][x] == 'S')
			{
				Sy = y;
				Sx = x;
			}
			// 대피소 위치 체크
			else if (map[y][x] == 'D')
			{
				Dy = y;
				Dx = x;
			}
		}
		getchar(); // enter
	}

	// 고슴도치를 큐에
	memset(checked, 0, sizeof(checked));
	que.push(point(Sy, Sx, 2)); // 고슴도치:type2
	checked[Sy][Sx] = 1;

	// que
	bool endFlag = false;
	bool failFlag = false;
	while (!que.empty())
	{
		// 현재 노드
		point now = que.front();
		que.pop();
		
		// 네 방향
		for (int dir = 0; dir < 4; dir++)
		{
			int nextY = now.y + moveparam[dir][0];
			int nextX = now.x + moveparam[dir][1];

			// 맵 바운더리
			if (nextY == -1 || nextX == -1 || nextY == h || nextX == w)
				// 스킵
				continue;

			// 돌
			if (map[nextY][nextX] == 'X')
				// 스킵
				continue;

			// 비버굴
			if (map[nextY][nextX] == 'D')
				//고슴도치 성공
				if (now.type == 2)
				{
					checked[nextY][nextX] = checked[now.y][now.x] + 1;
					endFlag = true;
					break;
				}
				// 물 스킵
				else
					continue;

			// 물
			if (now.type == 1)
				// 현위치 = 빈공간, 고슴도치
				if (map[nextY][nextX] == '.' || map[nextY][nextX] == 'S')
				{
					map[nextY][nextX] = '*';
					que.push(point(nextY, nextX, 1));
				}
			
			// 고슴도치
			if (now.type == 2)
				// 현위치 = 빈공간, 
				if (map[nextY][nextX] == '.' && checked[nextY][nextX] == 0)
				{
					map[nextY][nextX] = 'S';
					checked[nextY][nextX] = checked[now.y][now.x] + 1;
					que.push(point(nextY, nextX, 2));
				}
		}

		// 끝
		if (endFlag == true)
			break;

		// 조기종료 체크
		if (checkFail() == true)
		{
			printf("catch\n");
			printf("KAKTUS");
			return 0;
		}
	}

	if (endFlag == true)
	{
		printf("%d", checked[Dy][Dx]-1);

	}
	else
		printf("KAKTUS");

}

djm03178 6년 전 1

물이 먼저 큐에 들어가버려서, 고슴고치의 이동을 검사하기 전에 먼저 checkFail이 호출되어버립니다.

2 2

이 경우 고슴도치는 첫 번째 턴에 굴에 들어갈 수 있지만, 물이 먼저 이동하여

과 같은 맵을 만들어놓고 검사를 실시하기 때문에 여기서 fail 판정이 나버립니다.

20170620 6년 전 0

감사합니다...!

아주 중요한 포인트를 놓히고 문제를 풀었네요.

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

문제

문제

출처

ICPC

비버의 집이 1숲의 가장자리, 2바위, 3물 로 둘러쌓여 있으면 조기 종료한다..

20170620 6년 전 0

djm03178 6년 전 1

20170620 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말