색종이 붙이기

/* 1. undo를 해주면 level 설정 필요 x */
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
bool map[10][10];
int dp[10][10];
bool row_of_ones[5] = { 1, 1, 1, 1, 1 };
bool row_of_zeros[5];
int one_ctr;
unsigned ans = -1;
int coverage[6] = { 0, 1, 4, 9, 16, 25 };
int paper_ctr[6];
int paper_ctr_max[] = { -1, 5, 5, 5, 4, 4 };
bool vst[10][10];	/* 1 */
bool possible[6][10][10];
void bf(int rb, int cb, int tot_paper_ctr, int one_covered) {
	if (one_covered == one_ctr) {
		if (tot_paper_ctr < ans) {
			ans = tot_paper_ctr;
		}
		return;
	}
	if (tot_paper_ctr >= ans - 1) {
		return;
	}
	for (; rb < 10; ++rb) {
		for (; cb < 10; ++cb) {
			if (map[rb][cb]) {
				goto cover;
			}
		}
		cb = 0;
	}
	return;
cover:
	for (int size = 5; size >= 1; --size) {
		if (paper_ctr[size] == paper_ctr_max[size]) {
			continue;
		}
		if (!possible[size][rb][cb]) {
			continue;
		}
		if (memcmp(map[rb] + cb + 1, row_of_ones, sizeof(bool) * (size - 1))) {
			continue;
		}
		for (int r = rb; r < rb + size; ++r) {
			memset(map[r] + cb, 0, sizeof(bool) * size);
		}
		++paper_ctr[size];
		bf(rb, cb + 1, tot_paper_ctr + 1, one_covered + coverage[size]);
		--paper_ctr[size];
		for (int r = rb; r < rb + size; ++r) {
			memset(map[r] + cb, 1, sizeof(bool) * size);
		}
	}
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	for (int r = 0; r < 10; ++r) {
		for (int c = 0; c < 10; ++c) {
			cin >> map[r][c];
			if (map[r][c]) {
				++one_ctr;
				dp[r][c] = 1;
				possible[1][r][c] = true;
			}
		}
	}
	for (int r = 8; r >= 0; --r) {
		for (int c = 8; c >= 0; --c) {
			if (!dp[r][c]) {
				continue;
			}
			int min_tile = min({ dp[r + 1][c], dp[r][c + 1], dp[r + 1][c + 1] });
			if (min_tile) {
				dp[r][c] = min_tile + 1;
				for (int size = 2; size <= min(dp[r][c], 5); ++size) {
					possible[size][r][c] = 1;
				}
			}
		}
	}
	bf(0, 0, 0, 0);
	cout << (int)ans;
	return 0;
}