글 읽기 - 불!문제입니다. ㅜㅜ 시작하자마자 틀리다고 뜹니다ㅜㅜ

wjdwldud4190 7년 전 0

안녕하세요 .문제를 푸는데 틀린 이유를 모르겠어서 도움을 청합니다 ㅠㅠ

문제 예제 테케랑 제가 질문 검색 게시판에서 보고 돌려본 테스트 케이스 모두 맞게 돌아갑니다.

디버깅을 통해 제가 생각하는 로직대로 움직여서 답을 찾는 것을 확인했습니다.

그런데 채점할 때 시작하자 마자 틀렸습니다로 떠서 ..이유를 모르겠습니다.

도움을 주시면 감사하겠습니다 ㅠㅠㅠㅠㅠㅠㅠ너무궁금합니다 ㅠㅠ

/////////////////////////질문 검색 게시판을 이용해서 해 본 테스트 케이스//

1 1

3 3

.#.

#@#

.#.

3 3

...

.@.

...

3 3

.#.

#@#

.#*

8 3

########

#*@.....

########

5 6

##.##

#...#

#.#.#

#.#@#

#*#.#

#####

5 6

##.##

#...#

#.#.#

#*#@#

#.#.#

#####

5 6

##.##

#...#

#*#.#

#.#@#

#.#.#

#####

8 9

########

#......#

#.####.#

#.#@.#.#

#.##.#.#

#....#.#

######.#

.......#

########

5 3

##.##

#*.@#

#####

7 7

.......

.*#.##.

.##.##.

...@...

.##.##.

.##.#*.

.......

7 7

......*

.##.##.

...@...

.##.##.

*......

7 7

.*....*

.##.##.

...@...

.##.##.

.*....*

7 7

.......

*##.##*

.##.##.

...@...

.##.##.

*.....*

7 7

*....*.

.##.##.

...@...

.##.##.

*....*.

7 7

*.....*

.##.##.

...@...

.##.##.

*##.##*

.......

7 7

..#.#..

.*#.#*.

.##.##.

...@...

.##.##.

.*#.#*.

.......

7 7

.......

.*#.#*.

.##.###

...@...

.##.###

.*#.#*.

.......

7 7

.......

.*#.#*.

###.##.

...@...

###.##.

.*#.#*.

.......

7 7

.......

.*#.#*.

.##.##.

...@...

.##.##.

.*#.#*.

..#.#..

5 3

..#..

.@#*.

..#..

1
IMPOSSIBLE
2
IMPOSSIBLE
6
5
IMPOSSIBLE
IMPOSSIBLE
28
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
4
4
4
4
4
4
4
4
2

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <string>
#include <queue>
#include <cstring>
#define inf 999999
using namespace std;
queue<pair<int, int>>fire;
queue<pair<int, int>>person;

string room[1001];
int d[1001][1001];
int fvisit[1001][1001];

int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int w, h;
//불이 퍼져나가는 함수
void fire_bfs()
{
	int qs = fire.size();
	while (qs--)
	{
		int x = fire.front().first;
		int y = fire.front().second;
		fire.pop();

		for (int k = 0; k < 4; k++)
		{
			int nx = x + dx[k];
			int ny = y + dy[k];

			if (nx >= 0 && nx < h && ny >= 0 && ny<w&& room[nx][ny] != '*'&&room[nx][ny] != '#')
			{
				room[nx][ny] = '*';
				//fvisit[nx][ny] = 1;
				fire.push(make_pair(nx, ny));
			}
		}
	}
}
//사람이 갈 수 있는 공간 
int person_bfs()
{
	int qs = person.size();
	while (qs--)
	{
		int x = person.front().first;
		int y = person.front().second;
		person.pop();

		for (int k = 0; k < 4; k++)
		{
			int nx = x + dx[k];
			int ny = y + dy[k];

			if (nx < 0 || nx >= h || ny < 0 || ny >= w)//탈출한다. 
			{
				printf("%d\n", d[x][y]);
				return 1;
			}

			//탈출할 수 없고 다른 공간으로 갈 수 있을 때 
			else if (nx >= 0 && nx < h && ny >= 0 && ny < w&&room[nx][ny] == '.')
			{
				if (d[nx][ny] > d[x][y] + 1)
				{
					d[nx][ny] = d[x][y] + 1;
					person.push(make_pair(nx, ny));
				}
			}


		}
	}
}

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

	while (testcase--)
	{
		room->clear();
		while (!fire.empty())
			fire.pop();
		while (!person.empty())
			person.pop();

		scanf("%d %d", &w, &h);
		int x, y;

		for (int i = 0; i < h; i++)
		{
			cin >> room[i];

			for (int j = 0; j < w; j++)
			{
				d[i][j] = inf;
				//fvisit[i][j] = 0;
				if (room[i][j] == '@')
				{//사람이 있는 곳을 큐에 넣어준다. 
					person.push(make_pair(i, j));
					d[i][j] = 1;
				}
				else if (room[i][j] == '*')
				{//불이 있는 곳을 큐에 넣어준다. 
					fire.push(make_pair(i, j));
					//fvisit[i][j] = 1;
				}
			}
		}

		int ans;
		//불을 퍼지게 한 후 사람이 갈 수 있는 곳을 간다. 
		while (!fire.empty() || !person.empty())
		{
			fire_bfs();
			ans = person_bfs();//1을 리턴하면 탈출 성공 
			if (ans == 1)
				break;
		}

		if (ans == 1)
			continue;
		else
			printf("IMPOSSIBLE\n");

	}
	return 0;
}

sgchoi5 7년 전 1

http://gooddaytocode.blogspot....

엄청 답답하실듯... 요링크 보시면 대회 당시의 tc 답안 있으니 참고하시길...

yunsubaek 7년 전 1

person_bfs()에서 조건에 해당하지 않을 경우에도 리턴값이 필요합니다

wjdwldud4190 7년 전 1

@yunsubaek

답장감사합니다!!!그런데 혹시 조건을 만족하지 않을때가 어떤경우인지 알수있을까요?ㅠㅠ그런데 저는 사람이 한번 지나가면 다시 지나갈 수 없도록 짰는데..지나갔던길을 다시 지나가서 탈출하는경우도 있을까요..? 귀찮게 해드려서 죄송합니다..!ㅠㅠ

sgchoi5 7년 전 2

다시 지나가서 탈출하는경우 => 없습니다.. : )

wjdwldud4190 7년 전 0

@sgchoi5

댓글감사합니다ㅠㅠㅠ다른 질문 게시판에 올려주신 댓글 보고 테케 받아봤었어요ㅠㅠ

그런데 파일 형식이 .in .out이여서 안열려서 어떻게 처리해야 할지 몰라서 이용을 못했네요ㅠㅠ파일입출력을 해야하나 생각은 했는데..

낼 해봐야겠어요ㅠㅠ 가르쳐주셔서 정말 감사합니다!!

yunsubaek 7년 전 1

person_bfs()함수의 경우 큐의 사이즈를 구해놓고 크기만큼 돌리기 때문에 미리 들어가있는 사이즈에서 네방향 탐색을 합니다. 이때 여기에서 탈출(끝부분에 도착)할 수 없고 bfs가 끝나는 경우도 생깁니다. wjdwldud4190님 소스에서 이 경우만 return 0으로 처리하면 바로 해결되네요 ㅎㅎ

sgchoi5 7년 전 1

제 블로그 004 020 072 번 보시면 표준입출력을 file로 지정할수 있는 방법이 있어요

참고하시길

wjdwldud4190 7년 전 1

@yunsubaek

탈출 못하는 경우는 큐에 들어있는게 없으니까 알아서 끝날 줄 알고 리턴값을 지정 안했는데 여기서 오류가 날지 몰랐네요ㅠㅠ

해결했습니다!! 감사합니다ㅠㅠ 너무개운해요ㅜㅜ

wjdwldud4190 7년 전 0

@sgchoi5

헐!! 감사합니다ㅠㅠ안그래도 테케 어떻게 이용하는지 궁금했어요ㅜㅜ 감사합니다!!

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

문제

문제

출처

ICPC

불!문제입니다. ㅜㅜ 시작하자마자 틀리다고 뜹니다ㅜㅜ

wjdwldud4190 7년 전 0

sgchoi5 7년 전 1

yunsubaek 7년 전 1

wjdwldud4190 7년 전 1

sgchoi5 7년 전 2

wjdwldud4190 7년 전 0

yunsubaek 7년 전 1

sgchoi5 7년 전 1

wjdwldud4190 7년 전 1

wjdwldud4190 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말