글 읽기 - 17%에서 틀립니다. 혹시 좀 봐주실수 있나요?

kitri04 5년 전 0

board를 처음부터 스캔하다가 1을 만나면

그 위치에서 최대로 덮을 수 있는 색종이 크기를 구합니다.

만약 3이라면 2, 1은 자동으로 덮을수 있으니까요

그 상태에서 3 덮고(덮은 부분은 board에서 0으로 바꾸기)

또 1을 만나면 최대 덮을수 있는 크기를 구합니다.

그리고 처음부터 같은 과정을 반복합니다.

예시에서 처음 3이라고 했으니

3 덮고 쭉 진행하고 끝나면 2 덮고 쭉 진행, 그 후 1덮고 쭉 진행

그러면 모든 케이스에 대해 검사가 끝나고 그 때 최소값을 출력합니다.

#pragma warning (disable:4996)
#include <bits/stdc++.h>
using namespace std;

int board[10][10];
int cnt[6] = { 0,5,5,5,5,5 };
int selCnt;
int result = 26;

int calMaxSize(int y, int x)
{
	int w = 0;
	int h = 0;
	int max;

	for (int i = y; i < 10; ++i)
		if (board[i][x])
		{
			h++;
			if (h > 4)
				break;
		}
		else
			break;

	for (int i = x; i < 10; ++i)
		if (board[y][i])
		{
			w++;
			if (w > 4)
				break;
		}
		else 
			break;

	max = w > h ? h : w;

	bool isPossible = true;
	int limit = max;
	for (; limit > 0; --limit)
	{
		isPossible = true;
		for (int i = 0; i < max; ++i)
		{
			for (int j = 0; j < max; ++j)
			{
				if (!board[y + i][x + j])
				{
					isPossible = false;
					break;
				}
			}

			if (!isPossible)
				break;
		}
		if (isPossible)
			return limit;
	}

	/*if (isPossible)
		return limit;
	else
		return 1;*/
		
}

void doCover(int y, int x, int size, int val)
{
	for (int i = 0; i < size; ++i)
		for (int j = 0; j < size; ++j)
			board[y + i][x + j] = val;
}

void dfs(int y, int x, bool isEnd)
{
	if (isEnd)
		return;

	// 1 찾기
	bool isFind = false;
	for (int i = y; (i < 10) && !isFind; ++i)
	{
		for (int j = 0; j < 10; ++j)
		{
			if (board[i][j])
			{
				y = i;
				x = j;
				isFind = true;
				break;
			}
		}
	}

	// 더 이상 덮을 공간이 없다면 갱신
	if (!isFind)
	{
		if (result > selCnt)
			result = selCnt;
		return;
	}

	if (selCnt >= result)
		return;

	// 최대크기 계산
	int maxSize = calMaxSize(y, x);

	bool isCover = false;
	for (int i = maxSize; i > 0; --i)
	{
		// 덮기
		if (cnt[i] > 0)
		{

			isCover = true;
			--cnt[i];
			++selCnt;
			doCover(y, x, i, 0);
			dfs(y, x, false);
			
			// 되돌리기
			doCover(y, x, i, 1);
			--selCnt;
			++cnt[i];
			
		}
	}

	// 만약 안 덮은 곳이 있는데 더 이상 덮을 수 없다면
	if(!isCover)
		dfs(y, x, true);
}

int main()
{
	for (int i = 0; i < 10; ++i)
		for (int j = 0; j < 10; ++j)
			scanf("%d", &board[i][j]);

	dfs(0, 0, false);

	if (result == 26)
		printf("-1");
	else
		printf("%d", result);
}

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

문제

문제

출처

ICPC

17%에서 틀립니다. 혹시 좀 봐주실수 있나요?

kitri04 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말