글 읽기 - 3055번 C++ TC는 다 맞게 나오는데 틀렸습니다. 나와요 ㅠ 반례좀 주세요!

mycool0905 5년 전 1

비버 BFS 하고 물 BFS 하고 반복하는 형식입니다.

반례좀 알려주세요 ㅠㅠ

#include <iostream>
#include <cstdio>
#include <queue>
#include <utility>

using namespace std;

const int dx[4] = { 0,1,0,-1 };
const int dy[4] = { 1,0,-1,0 };
int R, C;
char field[50][50];
int BFS_count[50][50] = { 0, };

bool isIn(int x, int y)
{
	if (0 <= x && x < R && 0 <= y && y < C)
		return true;
	else
		return false;
}

int BFS(pair<int, int> start, pair<int, int> end, queue<pair<int, int>> wQueue)
{
	pair<int, int> newPair;
	queue<pair<int, int>> waterQueue = wQueue;
	queue<pair<int, int>> beaverQueue;
	vector<pair<int, int>> waterVector;
	vector<pair<int, int>> beaverVector;
	int wqSize, bqSize;
	int newX, newY;


	beaverQueue.push(start);

	while (!beaverQueue.empty())
	{
		wqSize = waterQueue.size();
		bqSize = beaverQueue.size();
		waterVector.clear();
		beaverVector.clear();

		for (int i = 0; i < bqSize; i++) // 비버 BFS 차례
		{
			beaverVector.push_back(beaverQueue.front());
			beaverQueue.pop();
		}

		for (int i = 0; i < bqSize; i++)
		{
			newPair = beaverVector[i];
			if (field[newPair.first][newPair.second] == 'S')
				for (int j = 0; j < 4; j++)
				{
					newX = newPair.first + dx[j];
					newY = newPair.second + dy[j];
					if (isIn(newX, newY))
						if (field[newX][newY] == '.')
						{
							field[newX][newY] = 'S';
							BFS_count[newX][newY] = BFS_count[newPair.first][newPair.second] + 1;
							beaverQueue.push(make_pair(newX, newY));
						}
						else if (field[newX][newY] == 'D') // 굴 만나면 BFS_count 리턴
							return BFS_count[newPair.first][newPair.second] + 1;
				}
		}

		for (int i = 0; i < wqSize; i++) // 물 BFS 차례
		{
			waterVector.push_back(waterQueue.front());
			waterQueue.pop();
		}

		for (int i = 0; i < wqSize; i++)
		{
			newPair = waterVector[i];
			for (int j = 0; j < 4; j++)
			{
				newX = newPair.first + dx[j];
				newY = newPair.second + dy[j];
				if (isIn(newX, newY))
					if (field[newX][newY] == '.' || field[newX][newY] == 'S')
					{
						field[newX][newY] = '*';
						waterQueue.push(make_pair(newX, newY));
					}
			}
		}
	}

	return -1;
}

int main()
{
	pair<int, int> start;
	pair<int, int> end;
	queue<pair<int, int>> water;
	int answer;

	cin >> R >> C;

	for (int i = 0; i < 50; i++)
		for (int j = 0; j < 50; j++)
			field[i][j] = NULL;

	for (int i = 0; i < R; i++)
		scanf("%s", field[i]);

	for (int i = 0; i < R; i++)
		for (int j = 0; j < C; j++)
			if (field[i][j] == 'D')
				end = make_pair(i, j);
			else if (field[i][j] == '*')
				water.push(make_pair(i, j));
			else if (field[i][j] == 'S')
				start = make_pair(i, j);

	answer = BFS(start, end, water);

	if (answer == -1)
		cout << "KAKTUS" << endl;
	else
		cout << answer << endl;

	return 0;
}

djm03178 5년 전 2

길이가 50인 문자열을 입력받기 위해서는 널 문자까지 최소한 51칸이 필요합니다.

11번째 줄을 char field[50][51]; 로 바꾸면 맞습니다.

mycool0905 5년 전 1

@djm03178

와 감사합니다.. 문자열로 받는걸 간과했네요..

좋은 답변 감사합니다! ^.^

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

문제

문제

출처

ICPC

3055번 C++ TC는 다 맞게 나오는데 틀렸습니다. 나와요 ㅠ 반례좀 주세요!

mycool0905 5년 전 1

djm03178 5년 전 2

mycool0905 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말