글 읽기 - 틀린 이유

leehanjun 7년 전 0

[알고리즘]

우선은 완전 탐색을 이용하였습니다.

그리고 1) 보석이 (N+1)이면 (N+1)개의 조각이 나와야 한다 사실과 2) 불순물이 N 개이면 (N+1)개의 조각을 만들 수 있다는 사실을 이용해서

불순물 개수 + 1 == 보석 개수를 만족해야 프로그램을 진행하도록 하였습니다.

그리고 가장 자리에 불순물이 들어가는 상황은 배제 하였습니다.

예를 들어

1 0 0

0 1 0

0 0 2

같은 상황은 배제 하였습니다.

[질문]

1) 위의 알고리즘이 적절한가?

2) 입력에서 보석이 한 개만 있는 상황이면 어떻게 되는가?

예를 들면

0 0 0

0 2 0

0 0 0

입니다.

아래 코드 제출합니다.

cut_board 부분만 읽어 주시면 감사하겠습니다.

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

// Global variables

int g_board[20][20];

/* to know it is possible to cut horizontally */

bool
is_possible_to_cut_horizontally (int& a_ny, int& a_x_begin, int& a_x_end)
{
	
	bool ret = true;
	
	for (int idx_x = a_x_begin; idx_x <= a_x_end; ++idx_x)
	{
		
		if (g_board[a_ny][idx_x] == 2)
		{
			ret = false;
			break;
		}
		
	}
	
	return ret;
	
}
 
/* to know it is possible to cut vertically */

bool
is_possible_to_cut_vertically (int& a_nx, int& a_y_begin, int& a_y_end)
{
	
	bool ret = true;
	
	for (int idx_y = a_y_begin; idx_y <= a_y_end; ++idx_y)
	{
		
		if (g_board[idx_y][a_nx] == 2)
		{
			ret =false;
		}
		
	}

	return ret;
	
}

/* to get the count of cutting_board */

int
cut_board (int a_y_begin, int a_y_end, int a_x_begin, int a_x_end, char a_method )
{
	
	// to check it is promising:
	int cnt_impurity, cnt_ruby;
	cnt_impurity = cnt_ruby = 0;
	
	for (int idx_y = a_y_begin; idx_y <= a_y_end; ++idx_y)
	{		
		for (int idx_x = a_x_begin; idx_x <= a_x_end; ++idx_x)
		{
			
			if (g_board[idx_y][idx_x] == 1)
			{
				++cnt_impurity;
			}
			
			else if (g_board[idx_y][idx_x] == 2)
			{
				++cnt_ruby;
			}
		
		}
	}
	
	// base case:
	if (cnt_impurity == 0 && cnt_ruby == 1)
	{
		return 1;
	}
	else if (cnt_impurity + 1 != cnt_ruby)
	{
		return -1;
	}
		
	// cut it off with two parties:
	int ret = 0;
	char method_next = 'h' + 'v' - a_method;
	
	for (int idx_y = a_y_begin; idx_y <= a_y_end; ++idx_y)
	{		
		for (int idx_x = a_x_begin; idx_x <= a_x_end; ++idx_x)
		{
			
			if (g_board[idx_y][idx_x] == 1 && method_next == 'h' && is_possible_to_cut_horizontally (idx_y, a_x_begin, a_x_end))
			{
				
				int cnt_upper, cnt_lower;
				
				cnt_upper = cut_board (a_y_begin, idx_y - 1, a_x_begin, a_x_end, method_next);
				cnt_lower = cut_board (idx_y + 1, a_y_end, a_x_begin, a_x_end, method_next);
				
				if (cnt_upper != -1 && cnt_lower != -1)
				{
					ret += cnt_upper * cnt_lower;	
				} 
				
				break;
				
			}
			
			else if (g_board[idx_y][idx_x] == 1 && method_next == 'v' && is_possible_to_cut_vertically (idx_x, a_y_begin, a_y_end))
			{
	
				int cnt_left, cnt_right;
				
				cnt_left = cut_board (a_y_begin, a_y_end, a_x_begin, idx_x - 1, method_next);
				cnt_right = cut_board (a_y_begin, a_y_end, idx_x + 1, a_x_end, method_next);
				
				if (cnt_left != -1 && cnt_right != -1)
				{
					ret += cnt_left * cnt_right;
				}
				
				break;
				
			}
			
		}
		
	}
	
	if (ret == 0)
	{
		return -1;
	}
	else
	{
		return ret;
	}
	
}	

void
set_board (int a_N)
{
	
	for (int idx_y = 0; idx_y < a_N; ++idx_y)
	{
		for (int idx_x = 0; idx_x < a_N; ++idx_x)
		{
			cin >> g_board[idx_y][idx_x];
		}
	}
	
}

int 
main ()
{
	
	int N;
	
	cin >> N;
	set_board (N);
	
	
	// get the result:
	int ret, cnt_vertical, cnt_horizontal;
	ret = 0;
	
	cnt_vertical = cut_board (0, N-1, 0, N-1, 'v');
	cnt_horizontal = cut_board (0, N-1, 0, N-1, 'h');
	
	if (cnt_vertical != -1)
	{
		ret += cnt_vertical;
	}
	
	if (cnt_horizontal != -1)
	{
		ret += cnt_horizontal;
	}
	
	// print result:
	if (ret == 0)
	{
		cout << -1 << endl;
	}
	else
	{
		cout << ret << endl;
	}
	
}

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

문제

문제

출처

ICPC

틀린 이유

leehanjun 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말