글 읽기 - 왜 틀렸다고 나오는지 도저히 모르겠습니다...

luckyhan1013 8년 전 0

여러가지 테스트케이스 만들어서 시도해 봤는데 다 답이 잘 나오는데 어떤 예외가 있는지 도저히 못찾겠네요

로직은 간단합니다.

고슴도치 시작점, 물의 시작점, 도착점을 각각 저장하고

BFS를 돌리면 고슴도치가 도착점에 도착할 경우 도착할때까지 걸린 시간을 출력하고

만약에 고슴도치가 도착하지 못하는경우(물이 고슴도치의 진로를 모두 막은 경우)

KAKTUS를 출력하게 됩니다. 큐에 물의 위치와 고슴도치 위치를 순서대로 삽입하여 물이 먼저 진행하게 되므로 문제에서 물과 고슴도치가 동시에 진행되는 점은 고슴도치가 못가는 위치로 간주되게 됩니다.

어떤 부분이 잘못된 것일까요?

#include <cstdio>
#include <cstdlib>
#include <queue>
#include <string.h>

using namespace std;

#define TYPE_WATER 1
#define TYPE_GOS 2

int r,c;
int map[51][51];

typedef struct _node{
	int x,y;
	int cnt;
	int type;
}node;

int gx,gy;
int wx,wy;
int dx,dy;


void bfs()
{
	queue<node> q;

	node n1;
	n1.x = wx;
	n1.y = wy;
	n1.cnt = 0;
	n1.type = TYPE_WATER;
	q.push(n1);

	node n2;
	n2.x = gx;
	n2.y = gy;
	n2.cnt = 0;
	n2.type = TYPE_GOS;
	q.push(n2);

	while(!q.empty())
	{
		node temp = q.front();
		q.pop();

		if(temp.x == dx && temp.y == dy && temp.type == TYPE_GOS)
		{
			printf("%d\n",temp.cnt);
			return;
		}

		if(temp.type == TYPE_WATER)
		{
			if(temp.x-1 > 0 && (map[temp.x-1][temp.y] == '.' || map[temp.x-1][temp.y] == 'g'))
			{
				node k;
				k.x = temp.x-1;
				k.y = temp.y;
				k.cnt = temp.cnt+1;
				k.type = temp.type;
				map[k.x][k.y] = '*';
				q.push(k);
			}
			if(temp.x+1 <= r && (map[temp.x+1][temp.y] == '.' || map[temp.x+1][temp.y] == 'g'))
			{
				node k;
				k.x = temp.x+1;
				k.y = temp.y;
				k.cnt = temp.cnt+1;
				k.type = temp.type;
				map[k.x][k.y] = '*';
				q.push(k);
			}
			if(temp.y-1 > 0 && (map[temp.x][temp.y-1] == '.' || map[temp.x][temp.y-1] == 'g'))
			{
				node k;
				k.x = temp.x;
				k.y = temp.y-1;
				k.cnt = temp.cnt+1;
				k.type = temp.type;
				map[k.x][k.y] = '*';
				q.push(k);
			}
			if(temp.y+1 <= c && (map[temp.x][temp.y+1] == '.' || map[temp.x][temp.y+1] == 'g'))
			{
				node k;
				k.x = temp.x;
				k.y = temp.y+1;
				k.cnt = temp.cnt+1;
				k.type = temp.type;
				map[k.x][k.y] = '*';
				q.push(k);
			}
		}else
		{
			if(temp.x-1 > 0 && (map[temp.x-1][temp.y] == '.' || map[temp.x-1][temp.y] == 'D'))
			{
				node k;
				k.x = temp.x-1;
				k.y = temp.y;
				k.cnt = temp.cnt+1;
				k.type = temp.type;
				map[k.x][k.y] = 'g';
				q.push(k);
			}
			if(temp.x+1 <= r && (map[temp.x+1][temp.y] == '.' || map[temp.x+1][temp.y] == 'D'))
			{
				node k;
				k.x = temp.x+1;
				k.y = temp.y;
				k.cnt = temp.cnt+1;
				k.type = temp.type;
				map[k.x][k.y] = 'g';
				q.push(k);
			}
			if(temp.y-1 > 0 && (map[temp.x][temp.y-1] == '.' || map[temp.x][temp.y-1] == 'D')) 
			{
				node k;
				k.x = temp.x;
				k.y = temp.y-1;
				k.cnt = temp.cnt+1;
				k.type = temp.type;
				map[k.x][k.y] = 'g';
				q.push(k);
			}
			if(temp.y+1 <= c && (map[temp.x][temp.y+1] == '.' || map[temp.x][temp.y+1] == 'D'))
			{
				node k;
				k.x = temp.x;
				k.y = temp.y+1;
				k.cnt = temp.cnt+1;
				k.type = temp.type;
				map[k.x][k.y] = 'g';
				q.push(k);
			}
		}
	}

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


int main()
{
	scanf("%d%d",&r,&c);

	for(int x=1; x<=r;x++)
	{
		for(int y=1;y<=c;y++)
		{
			int ch = getc(stdin);
			if(ch=='\n'||ch=='\r')
			{
				y--;
				continue;
			}
			if(ch=='S')
			{
				gx=x;
				gy=y;
			}
			if(ch=='*')
			{
				wx=x;
				wy=y;
			}
			if(ch=='D')
			{
				dx=x;
				dy=y;
			}
			map[x][y] = ch;
		}
	}

	bfs();

	return 0;

}

luckyhan1013 8년 전 0

자체 해결 했습니다...

물이 고여있는 포인트가 여러개일수도 있군요... 한군데만 있는 줄 알았는데....

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

문제

문제

출처

ICPC

왜 틀렸다고 나오는지 도저히 모르겠습니다...

luckyhan1013 8년 전 0

luckyhan1013 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말