글 읽기 - 이 코드를 돌아가게 만들고 싶습니다.

kritias 3년 전 0

구슬탈출 1, 2, 3번까지 이 코드를 응용해서 풀었습니다.

응용한 점은 check[10][10][10][10] 배열을 이용해 해당 재귀에서 두번이상 같은 R,B포지션을 만들지 않도록 한 점인데 이 부분에서 문제가 있는 것 같습니다.

반례들을 넣어보면 모두 정답은 잘 나오는데 특정 경우를 수행하지 못해서 재귀문을 빠져나오지 못하는 경우가 있습니다.

10 8
########
##..RB##
#.....##
#####..#
#.#.O..#
#.....##
#..#.#.#
##.#...#
##....##
########

위의 경우, R의 포지션이 4, 5, B의 포지션이 5, 5일 때 오른쪽을 탐색하고는 왼쪽을 끝까지 탐색하지 않아서 정답이 나오지 않습니다.

다른 반례들도 정답이 나오거나 영원히 끝나지 않거나 둘 중 하나라서 너무 아쉽습니다. ㅠㅠ

혹시 고수분이 이걸 보신다면 해결책을 찾아주셨으면 좋겠습니다!

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
void init()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
}

int n, m;
bool check[10][10][10][10] = { false };

stack<int> simul(vector<vector<char>> table, int dirX, int dirY)
{
	#pragma region 초기화 및 볼 위치 저장
	stack<int> result;
	bool fallR = false, fallB = false;
	bool endR = false, endB = false;
	int rx, ry, bx, by;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			switch (table[i][j])
			{
			case 'R':
				rx = i;
				ry = j;
				break;
			case 'B':
				bx = i;
				by = j;
				break;
			}
		}
	}
	#pragma endregion
	#pragma region 볼 이동 부분
	if (dirX != dirY)
		while (!endR || !endB)
		{
			if (!endR)
			{
				switch (table[rx + dirX][ry + dirY])
				{
				case '.':
					table[rx][ry] = '.';
					rx += dirX;
					ry += dirY;
					table[rx][ry] = 'R';
					break;
				case 'O':
					table[rx][ry] = '.';
					fallR = endR = true;
					break;
				case '#':
					endR = true;
					break;
				case 'B':
					endR = endB;
					break;
				}
			}
			if (!endB)
			{
				switch (table[bx + dirX][by + dirY])
				{
				case '.':
					table[bx][by] = '.';
					bx += dirX;
					by += dirY;
					table[bx][by] = 'B';
					break;
				case 'O':
					table[bx][by] = '.';
					fallB = endB = true;
					break;
				case '#':
					endB = true;
					break;
				case 'R':
					endB = endR;
					break;
				}
			}
		}
	#pragma endregion
	#pragma region 시행 종료 체크
	if (fallB || (check[rx][ry][bx][by] && !fallR))
	{
		return result;
	}
	if (fallR)
	{
		result.push(dirX * 2 + dirY);
		return result;
	}
	#pragma endregion
	#pragma region 현재 위치부터 재귀 수행
	check[rx][ry][bx][by] = true;
	stack<int> resStack[4];
	if (dirX == 0)
	{
		resStack[0] = simul(table, 1, 0);
		resStack[1] = simul(table, -1, 0);
	}
	if (dirY == 0)
	{
		resStack[2] = simul(table, 0, 1);
		resStack[3] = simul(table, 0, -1);
	}
	check[rx][ry][bx][by] = false;
	#pragma endregion
	#pragma region 최소 사이즈 스택 반환
	stack<int> minStack;
	for (stack<int> candidate : resStack)
	{
		if ((minStack.size() == 0 || minStack.size() > candidate.size()) && candidate.size())
		{
			minStack = candidate;
		}
	}
	if (minStack.size())
	{
		minStack.push(dirX * 2 + dirY);
		return minStack;
	}
	return result;
	#pragma endregion
}

int main(void)
{
	init();
	int rx = 0, ry = 0, bx = 0, by = 0;
	cin >> n >> m;
	vector<vector<char>> table(n);
	for (int i = 0; i < n; i++)
	{
		table[i].resize(m);
		for (int j = 0; j < m; j++)
		{
			cin >> table[i][j];
		}
	}
	stack<int> ans = simul(table, 0, 0);
	if (!ans.empty())
	{
		cout << ans.size() - 1 << '\n';
		
		char resTable[] = { 'U', 'L', 'O', 'R', 'D' };
		if (!ans.empty())
		{
			ans.pop();
			while (!ans.empty())
			{
				cout << resTable[ans.top() + 2];
				ans.pop();
			}
		}
		
	}
	else cout << -1;
	return 0;
}

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

문제

문제

출처

ICPC

이 코드를 돌아가게 만들고 싶습니다.

kritias 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말