글 읽기 - 사다리조작 반례

songvic 5년 전 0

주어진 예제 코드 전부 돌아가는데 틀렸습니다.

반례를 찾아주세요!

#include <iostream>
#include <set>
#include <vector>
using namespace std;

struct data_type
{
	int a; int b;
};

int a[30][10]; 
int n; int m; int h;
int ans = 99999999;

// 사다리 타기
void go()
{
	cout << endl;
	for (int x = 0; x < n; x++)
	{
		int start = x;
		for (int y = 0; y < h; y++)
		{
			cout << start << " ";
			if (a[y][start] != -1)
			{
				start = a[y][start];
			}
		}
		cout << endl;
	}
}

void print()
{
	cout << endl;
	for (int y = 0; y < h; y++)
	{
		for (int x = 0; x < n; x++)
		{
			cout << a[y][x] << " ";
		}
		cout << endl;
	}
}

bool check()
{
	int x;
	for (x = 0; x < n; x++)
	{
		int start = x; int current = x;
		for (int y = 0; y < h; y++)
		{
			if (a[y][current] != -1)
			{
				current = a[y][current];
			}
		}
		if (current != start) break;
	}

	return x == n;
}
void dfs(int y, int x, int cnt)
{
	if (cnt > 3) return;

	if (check())
	{
		if (ans > cnt) ans = cnt;
		return;
	}

	if (x >= n - 2)
	{
		x = 0;  y += 1;
	}
	for (int cy = y; cy < h; cy++)
	{
		for (int cx = x; cx < n - 1; cx++)
		{
			// 연속을 제외한 가로 사다리 만들기	
			if (a[cy][cx] == -1 && a[cy][cx + 1] == -1)
			{
				a[cy][cx] = cx + 1;
				a[cy][cx + 1] = cx;
				dfs(cy, cx + 2, cnt + 1);
				a[cy][cx] = -1;
				a[cy][cx + 1] = -1;
			}
		}
	}
}

int main()
{
	vector<data_type> vp;

	// 입력
	cin >> n >> m >> h;
	for (int i = 0; i < m; i++)
	{
		data_type dt;
		cin >> dt.a >> dt.b;
		dt.a -= 1; dt.b -= 1;
		vp.push_back(dt);
	}

	// 사다리 만들기
	for (int y = 0; y < h; y++)
	{
		for (int x = 0; x < n; x++)
		{
			a[y][x] = -1;
		}
	}
	for (int i = 0; i < m; i++)
	{
		a[vp[i].a][vp[i].b] = vp[i].b + 1;
		a[vp[i].a][vp[i].b + 1] = vp[i].b;
	}

	dfs(0, 0, 0);

	if (ans == 99999999) ans = -1;
	cout << ans << endl;

	return 0;
}

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

문제

문제

출처

ICPC

사다리조작 반례

songvic 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말