글 읽기 - 반례 혹은 로직의 보완점 부탁드립니다.

hus5522 1년 전 0

진행률 60%에서 컷 당하네요, 제가 놓친 것이 있나봅니다. 여러분의 지혜를 나눠주세요.

발생할 수 있는 모든 경우의 수를 찾겠다는 의도로 짠 코드입니다

(board 의 실제 값은 변경하지 않습니다)

10번 이상의 이동이 있었거나, 2개가 동시에 떨어지거나, 1개만 떨어졌을 때 재귀를 종료하도록 구현했습니다.

#include <iostream>
using namespace std;

char board[20][20];
pair<int, int> coin[2] = { {-1, -1}, {-1, -1} };
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };
int n, m;
int answer = -1;

void moveCoin(const int& num, int cnt)
{
	if (cnt > 10)
		return;

	pair<int, int> c1 = coin[0];
	pair<int, int> c2 = coin[1];

	int x1 = c1.first + dx[num];
	int y1 = c1.second + dy[num];
	int x2 = c2.first + dx[num];
	int y2 = c2.second + dy[num];

	bool drop1 = ((0 <= x1 && x1 < n) && (0 <= y1 && y1 < m)) ? false : true;
	bool drop2 = ((0 <= x2 && x2 < n) && (0 <= y2 && y2 < m)) ? false : true;

	bool onlyone = ((drop1 && !drop2) || (!drop1 && drop2)) ? true : false;
	bool bothdrop = (drop1 && drop2);

	if (bothdrop)
		return;

	if (onlyone)
	{
		if (-1 == answer)
			answer = cnt + 1;
		else
			answer = (answer > cnt + 1) ? cnt + 1 : answer;

		return;
	}
	else
	{
		if (board[x1][y1] == '.' || board[x1][y1] == 'o')
			coin[0] = { x1, y1 };

		if (board[x2][y2] == '.' || board[x2][y2] == 'o')
			coin[1] = { x2, y2 };

		moveCoin(0, cnt + 1);
		moveCoin(1, cnt + 1);
		moveCoin(2, cnt + 1);
		moveCoin(3, cnt + 1);

		if (board[x1][y1] == '.' || board[x1][y1] == 'o')
			coin[0] = c1;

		if (board[x2][y2] == '.' || board[x2][y2] == 'o')
			coin[1] = c2;
	}
}

int main()
{
	cin.tie(0)->sync_with_stdio(false);

	cin >> n >> m;

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			cin >> board[i][j];

			if (board[i][j] == 'o')
			{
				if (coin[0].first == -1)
					coin[0] = make_pair(i, j);
				else
					coin[1] = make_pair(i, j);
			}
		}
	}

	moveCoin(0, 0);
	moveCoin(1, 0);
	moveCoin(2, 0);
	moveCoin(3, 0);

	cout << answer << "\n";

	return 0;
}

semi0777 1년 전 0

제가 이 문제를 풀어보진않았지만 동전간에 x와 y축의 차이가 있는만큼 떨어질 수 있는 출구간의 차이가 있지않은이상 동시에 떨어지지않을테니 그런 조건을 피하는 출구로부터 동전까지의 거리를 계산하거나 혹은 그런 조건의 출구이지만 한쪽의 길이 막혀있는지를 확인해서 그 길이가 가장 짧은 길을 도출하도록 하는건 어떠신가요?

semi0777 1년 전 0

근데 그러면 예제 5번은 예외처리를 좀 해야겠네요

osthus 1년 전 2

반례입니다.

7 6
######
##o..#
####.#
#o##.#
####.#
.....#
######

// 출력값: 11
// 정답: -1

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

문제

문제

출처

ICPC

반례 혹은 로직의 보완점 부탁드립니다.

hus5522 1년 전 0

semi0777 1년 전 0

semi0777 1년 전 0

osthus 1년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말