글 읽기 - 6593 상범빌딩 문제 반례가 존재하는지 궁금합니다(c++)

inhadong 4년 전 0

안녕하세요

많은 테스트 케이스를 돌려보고 확인해봤는데

계속 틀렸습니다라는 결과가 나오네요..

제 코드에 반례를 알고 싶습니다 알려주시면 감사하겠습니다.

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
int floorr;
int height;
int width;
int hi;
int dx[6] = {0,0,1,-1,0,0};
int dy[6] = {0,0,0,0,1,-1};
int dz[6] = {1,-1,0,0,0,0};
char arr[31][31][31];
int check[31][31][31];

struct xyz
{
	int z;
	int x;
	int y;
};

queue<xyz> q;

int bfs()
{
	xyz obj;
	while (!q.empty())
	{
		int fx = q.front().x;
		int fy = q.front().y;
		int fz = q.front().z;
		q.pop();
		for (int k = 0; k < 6; k++)
		{
			int nx = fx + dx[k];
			int ny = fy + dy[k];
			int nz = fz + dz[k];
			if (nx < 0 || ny < 0 || nz < 0 || nx >= height || ny >= width || nz >= floorr)
			{
				continue;
			}
			if (check[nz][nx][ny]==0)
			{
				check[nz][nx][ny] = check[fz][fx][fy] + 1;
				obj.x = nx;
				obj.y = ny;
				obj.z = nz;
				q.push(obj);
			}
			if (check[nz][nx][ny] == -2)
			{
				return check[fz][fx][fy];
			}
		}
	}
	return -1;
}

//배열을 초기화 해주는 함수
void initialize()
{
	for (int i = 0; i < floorr; i++)
	{
		for (int j = 0; j < height; j++)
		{
			for (int k = 0; k < width; k++)
			{
				check[i][j][k] = 0;
			}
		}
	}
	for (int i = 0; i < floorr; i++)
	{
		for (int j = 0; j < height; j++)
		{
			for (int k = 0; k < width; k++)
			{
				arr[i][j][k] = NULL;
			}
		}
	}
}

void print()
{
	for (int i = 0; i < floorr ; i++)
	{
		for (int j = 0; j < height; j++)
		{
			for (int k = 0; k < width; k++)
			{
				cout << check[i][j][k] << " ";
			}
			cout << endl;
		}
		cout << endl;
	}
}

int main()
{
	int answer;
	while (true)
	{
		cin >> floorr >> height >> width;
		if (floorr == 0 && height == 0 && width == 0)
		{
			break;
		}

		for (int i = 0; i < floorr; i++)
		{
			for (int j = 0; j < height; j++)
			{
				for (int k = 0; k < width; k++)
				{
					cin >> arr[i][j][k];
				}
			}
		}

		for (int i = 0; i < floorr; i++)
		{
			for (int j = 0; j < height; j++)
			{
				for (int k = 0; k < width; k++)
				{
					if (arr[i][j][k] == 'S')
					{
						xyz object;
						object.x = j;
						object.y = k;
						object.z = i;
						check[i][j][k] = 1;
						q.push(object);
					}
				}
			}
		}

		for (int i = 0; i < floorr; i++)
		{
			for (int j = 0; j < height; j++)
			{
				for (int k = 0; k < width; k++)
				{
					if (arr[i][j][k] == '#')
					{
						check[i][j][k] = -1;
					}
					if (arr[i][j][k] == 'E')
					{
						check[i][j][k] = -2;
					}
				}
			}
		}
		answer = bfs();
		if (answer ==-1)
		{
			 printf("Trapped!\n");
		}
		else
		{
			printf("Escaped in %d minute(s).\n", answer);
		}
		initialize();
	}
	return 0;
}

eovh1962 4년 전 0

큐를 비워주세요

//배열을 초기화 해주는 함수
void initialize()
{
	for (int i = 0; i < floorr; i++)
	{
		for (int j = 0; j < height; j++)
		{
			for (int k = 0; k < width; k++)
			{
				check[i][j][k] = 0;
			}
		}
	}
	for (int i = 0; i < floorr; i++)
	{
		for (int j = 0; j < height; j++)
		{
			for (int k = 0; k < width; k++)
			{
				arr[i][j][k] = NULL;
			}
		}
	}
	while (!q.empty())
	{
		q.pop();
	}
}

inhadong 4년 전 0

감사합니다 bfs가 중간에 끝나고 return되는 것을 간과했네요 ㅠㅠ

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

문제

문제

출처

ICPC

6593 상범빌딩 문제 반례가 존재하는지 궁금합니다(c++)

inhadong 4년 전 0

eovh1962 4년 전 0

inhadong 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말