글 읽기 - 17136 색종이 붙이기 17% 실패 질문드립니다.

smgod 4년 전 0

테스트케이스는 다맞췄는데 17퍼 에서 계속 틀렸다고 나옵니다. 어느 부분을 잘못했는지 알려주세요 ㅠㅠ

visit[i][j][k] = 그래프 i 행 j 열이 1일때 k값이 0 ~ 4에따라 0 = 1개짜리 붙일 수 있음

1 = 2개짜리 붙일 수 있음

2 = 3개짜리(3*3) 붙일 수 있음 ... 이렇게 우선 저장하고

bfs 형식으로 전체돌면서 색종이를 붙이게 코딩했습니다.

vi[i][j] 는 방문했는지를 체크하기 위해 만들어놓았습니다.

cnt[k]는 k값이 0~ 4에따라 1번 - 5번종이를 몇개사용했는지 확인합니다.

#include <stdio.h>
#include <iostream>
#include <cstring>

using namespace std;
int graph[10][10];
int g_cnt = 0;
int visit[10][10][5] = { 0, };
int vi[10][10] = { 0, };
int cnt[5] = { 0, };
int g_min = 5555;
void bfs()
{
	int tt = 0;
	if (g_cnt > g_min)
	{
		return;
	}
	for (int i = 0; i < 10; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			if (vi[i][j] == 1)
			{
				tt = 1;
				break;
			}
		}
		if (tt == 1)
			break;
	}
	if (tt == 0)// 다 칠했따면
	{
		if (g_cnt < g_min)
		{
			g_min = g_cnt;
		}
		return;
	}
	for (int i = 0; i < 10; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			if (graph[i][j] == 1 && vi[i][j] == 1) // graph 는 1이고 비짓 x일때
			{
				for (int k = 4; k >= 0; k--)
				{
					if (visit[i][j][k] == 1 && cnt[k] <= 4)
					{
						cnt[k] ++;
						g_cnt++;
						for (int t = i; t < i + k + 1; t++)
						{
							for (int u = j; u < j + k + 1; u++)
								vi[t][u] = 2;
						}
						bfs();
						for (int t = i; t < i + k + 1; t++)
						{
							for (int u = j; u < j + k + 1; u++)
								vi[t][u] = 1;
						}
						g_cnt--;
						cnt[k] --;
					}
				}
				return;

			}
		}
	}



}
int main(void)
{
	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 10; j++)
			std::cin >> graph[i][j];
	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 10; j++)
		{
			if (graph[i][j] == 1)
			{
				vi[i][j] = 1;
				visit[i][j][0] = 1;
				int tmp = 0;
				for (int y = i; y < i + 2 && y < 10; y++)
				{
					for (int x = j; x < j + 2 && x < 10; x++)
					{
						if (graph[y][x] == 1)
						{
							tmp++;
						}
					}
				}
				if (tmp == 4)
					visit[i][j][1] = 1; // 2개짤가능


				tmp = 0;
				for (int y = i; y < i + 3 && y < 10; y++)
				{
					for (int x = j; x < j + 3 && x < 10; x++)
					{
						if (graph[y][x] == 1)
						{
							tmp++;
						}
					}
				}
				if (tmp == 9)
					visit[i][j][2] = 1; // 3개짤가능

				tmp = 0;
				for (int y = i; y < i + 4 && y < 10; y++)
				{
					for (int x = j; x < j + 4 && x < 10; x++)
					{
						if (graph[y][x] == 1)
						{
							tmp++;
						}
					}
				}
				if (tmp == 16)
					visit[i][j][3] = 1; // 3개짤가능

				tmp = 0;
				for (int y = i; y < i + 5 && y < 10; y++)
				{
					for (int x = j; x < j + 5 && x < 10; x++)
					{
						if (graph[y][x] == 1)
						{
							tmp++;
						}
					}
				}
				if (tmp == 25)
					visit[i][j][4] = 1; // 3개짤가능
			}
		}

	bfs();
	if (g_min == 5555)
	{
		printf("-1");
	}
	else
		printf("%d", g_min);

	return 0;
}

rhdqor213 4년 전 11

반례입니다

1 1 1 1 1 1 0 0 0 0

0 0 0 0 0 0 0 0 0 0

답:6(4*4 2개, 2*2 4개)

코드 출력:5

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

문제

문제

출처

ICPC

17136 색종이 붙이기 17% 실패 질문드립니다.

smgod 4년 전 0

rhdqor213 4년 전 11

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말