글 읽기 - 유기농 배추 질문입니다.

jaykay 7년 전 0

생각할 수 있는 예제는 다 넣어봤는데

어느 부분에서 틀렸는지 모르겠네요.

좌표는 x + y * 50 으로 표현하였고 set 과 find 를 이용해서 상하좌우 좌표를 찾아 자신과 그리고 인접한 좌표를 erase 시키는 방법으로 코드를 작성했습니다.

#include <fstream>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

const int UNIT = 50;

set<int> points;
int maxPosition;

int getNextPosition(int position, int direction)
{
	int ret = position;
	switch (direction)
	{
	case 0:
		ret -= UNIT;
		break;
	case 1:
		ret++;
		break;
	case 2:
		ret += UNIT;
		break;
	case 3:
		ret--;
		break;
	default:
		break;
	}

	if (ret < 0 || ret > maxPosition)
		return -1;
	return ret;
}

void recursive(int position)
{
	points.erase(position);
	for (int i = 0; i < 4; i++)
	{
		int temp = getNextPosition(position, i);

		if (temp != -1)
		{
			set<int>::iterator it = points.find(temp);
			if (it != points.end())
				recursive(temp);
		}
	}
}

int solve()
{
	int ret = 0;
	while (true)
	{
		if (points.empty())
			break;
		
		ret++;
		set<int>::iterator it = points.begin();
		recursive(*it);
	}

	return ret;
}

int main()
{
	int cases;
	cin >> cases;
	for (int i = 0; i < cases; i++)
	{
		int m, n, k;
		points.clear();
		cin >> m >> n >> k;
		maxPosition = m - 1 + (n - 1) * UNIT;
		for (int i = 0; i < k; i++)
		{
			int x, y;
			cin >> x >> y;
			points.insert(x + y * UNIT);
		}

		cout << solve() << endl;
	}

	return 0;
}

dbtmddus112 7년 전 1

const int UNIT = 50;
부분에서 , UNIT을 50보다는 큰 값으로 설정하셔야 합니다

input을

1
50 50 4
0 0
0 49
0 1
49 0

으로 주는 경우를 보시면, 정상값 3이 아닌 2가 출력되는 걸 확인할 수 있으실텐데,
작성자분은 points에 x + y * UNIT값 상태로 저장하시기 때문에,
가로, 세로 max 값이 50인경우
(0 1) = 50 입니다. 여기서 getnextnextposition 함수로 들어가면 왼칸을 보는 경우 50-- = 49 로 넘어가는데,
49는 (49, 0)을 의미하게 됩니다.

즉, max값이 50인 경우 (0 1)의 왼칸이 (0 49) 를 의미하게 됩니다.
max가 50인 경우에도 값이 겹치지 않게 하기 위해, unit을 50이 넘는 수로 지정하셔야 합니다.

jaykay 7년 전 0

저 경우를 생각하지 못 했군요 ㅠㅠ 해결됬습니다 감사합니다 ^^

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

문제

문제

출처

ICPC

유기농 배추 질문입니다.

jaykay 7년 전 0

dbtmddus112 7년 전 1

jaykay 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말