<백준> 17136

색종이 붙이기

문제

입력
총 10개의 줄에 종이의 각 칸에 적힌 수가 주어진다.

출력
모든 1을 덮는데 필요한 색종이의 최소 개수를 출력한다. 1을 모두 덮는 것이 불가능한 경우에는 -1을 출력한다.

int m[10][10];
int v[6] = { 0,5,5,5,5,5 };
int result = INT_MAX;

bool Check(int x, int y, int size)
{
	if (x + size > 10 || y + size > 10)
		return false;
	for (int i = y; i < y + size; i++)
	{
		for (int j = x; j < x + size; j++)
		{
			if (m[i][j] != 1)
				return false;
		}
	}
	return true;
}

void Fill(int x, int y, int size, int num)
{
	for (int i = y; i < y + size; i++)
	{
		for (int j = x; j < x + size; j++)
		{
			m[i][j] = num;
		}
	}
}

void BackTracking(int xy, int count)
{
	if (xy == 100)
	{
		result = min(result, count);
		return;
	}

	int x = xy % 10;
	int y = xy / 10;

	if (result <= count)
		return;

	if (m[y][x] == 1)
	{
		for (int i = 5; i > 0; i--)
		{
			if (v[i] > 0 && Check(x, y, i))
			{
				v[i]--;
				Fill(x, y, i, 0);
				BackTracking(xy + 1, count + 1);
				v[i]++;
				Fill(x, y, i, 1);
			}
		}
	}
	else
	{
		BackTracking(xy + 1, count);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	for (int i = 0; i < 10; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			cin >> m[i][j];
		}
	}

	BackTracking(0, 0);

	if (result == INT_MAX)
		cout << -1;
	else
		cout << result;
}