글 읽기 - 뭐가 틀렸는지 알 수 잇을까요?

sbillards 4년 전 0

제 코드인데, 21개의 TC 나와있는것은 정상적으로 출력하고 있습니다.

7 5

...#*

..##.

##.#.

#@...

##.#.

..##.

...#*

이 테스트 케이스에서 이상한 답이 나오네요..

#define MAX_INF 10004

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

int T;
int w, h;

char cMap[1002][1002];
int nCheck[1002][1002];

int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };

vector<int> v;
queue<pair<int, int>> qFire;
queue<pair<int, int>> qDog;

void BFS(int nDepth)
{
	nCheck[qDog.front().first][qDog.front().second] += 1;
	int nTemp = 0;
	while (1)
	{
		nTemp = qFire.size();

		for (int k = 0; k < nTemp; k++)
		{
			int cFireY = qFire.front().first;
			int cFireX = qFire.front().second;

			qFire.pop();

			for (int i = 0; i < 4; i++)
			{
				int nFireY = cFireY + dy[i];
				int nFireX = cFireX + dx[i];

				if (nFireY >= 1 && nFireY <= h && nFireX >= 1 && nFireX <= w)
				{
					if (cMap[nFireY][nFireX] == '.')
					{
						cMap[nFireY][nFireX] = '*';
						qFire.push(make_pair(nFireY, nFireX));
					}
				}
			}
		}

		nTemp = qDog.size();
		for (int k = 0; k < nTemp; k++)
		{
			int cDogY = qDog.front().first;
			int cDogX = qDog.front().second;
			qDog.pop();

			// nCheck[cDogY][cDogX] += 1;

			if (cDogY == 1 || cDogY == h || cDogX == 1 || cDogX == w)
			{
				v[nDepth] = min(v[nDepth], nCheck[cDogY][cDogX]);
			}

			for (int i = 0; i < 4; i++)
			{
				int nDogY = cDogY + dy[i];
				int nDogX = cDogX + dx[i];

				if (nDogY >= 1 && nDogY <= h && nDogX >= 1 && nDogX <= w)
				{
					if (cMap[nDogY][nDogX] == '.' && nCheck[nDogY][nDogX] == 0)
					{
						nCheck[nDogY][nDogX] = nCheck[cDogY][cDogX] + 1;
						qDog.push(make_pair(nDogY, nDogX));
					}
				}

			}
		}

		if (qDog.empty() && qFire.empty())
		{
			break;
		}
	}
}
int main(void)
{
	cin >> T;

	v.assign(T, MAX_INF);
	for (int i = 0; i < T; i++)
	{

		cin >> w >> h;
		for (int y = 1; y <= h; y++)
		{
			for (int x = 1; x <= w; x++)
			{
				cin >> cMap[y][x];
			}
		}

		for (int y = 1; y <= h; y++)
		{
			for (int x = 1; x <= w; x++)
			{
				if (cMap[y][x] == '@')
				{
					qDog.push(make_pair(y, x));
				}
				if (cMap[y][x] == '*')
				{
					qFire.push(make_pair(y, x));
				}
			}
		}
		BFS(i);

		memset(cMap, 0, sizeof(cMap));
		memset(nCheck, 0, sizeof(nCheck));
	}

	for (int i = 0; i < T; i++)
	{
		if (v[i] == MAX_INF)
		{
			cout << "IMPOSSIBLE" << endl;
		}
		else
		{
			cout << v[i] << endl;
		}
	}


	return 0;
}

ghjo92 4년 전 0

위에 적으신 해당 테스트 케이스는 옳지 않은 입력입니다.

7열 5행으로 입력을 하고 싶으시다면

7과 5의 위치를 바꿔서 입력해보세요.

위의 코드로 해당 테스트케이스를 바르게 넣어보니 Impossible 잘 나옵니다.

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

문제

문제

출처

ICPC

뭐가 틀렸는지 알 수 잇을까요?

sbillards 4년 전 0

ghjo92 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말