题目描述

Frugal先生的新房子客厅地板由 $W \times H$ 的方形面板组成，部分面板有划痕（标记为 $1$），需要用地毯覆盖。地毯是正方形的，尺寸必须是面板大小的整数倍，可以重叠但不能折叠。要求用最少的地毯覆盖所有划痕面板，且不能覆盖完好面板（标记为 $0$）。求最少需要多少块地毯。

输入格式

• 多组数据，每组数据第一行为 $W$ 和 $H$（$1 \leq W, H \leq 10$）。
• 接下来 $H$ 行，每行 $W$ 个数字（$0$ 或 $1$），表示地板状态。
• 输入以 0 0 结束。

输出格式

对每组数据，输出最少需要的地毯数量。

解题思路

关键观察

1. 地毯性质：地毯是正方形，尺寸为 $k \times k$（$k \geq 1$），必须完全覆盖划痕区域，不能覆盖完好面板。
2. 贪心不可行：直接尝试用最大可能的地毯覆盖可能无法得到最优解，例如样例1中最大地毯只能覆盖部分区域。
3. 问题转化：可以看作是一个集合覆盖问题，需要用最少的正方形覆盖所有 $1$，且这些正方形不能覆盖 $0$。

算法选择

由于 $W$ 和 $H$ 较小（$\leq 10$），可以采用回溯+剪枝的方法：

1. 枚举所有可能的地毯：对于每个划痕面板 $(i,j)$，尝试所有可能的正方形地毯，以 $(i,j)$ 为左上角，边长 $k$ 从 $1$ 到最大可能值（不超出地板且不覆盖 $0$）。
2. 选择覆盖最多未覆盖点的地毯：优先选择能覆盖最多未被覆盖的 $1$ 的地毯，减少后续需要覆盖的点数。
3. 回溯搜索：递归尝试每个可能的地毯选择，记录最少数量。

优化

• 记忆化：缓存已经计算过的状态，避免重复计算。
• 剪枝：如果当前地毯数量已经超过已知的最小值，直接返回。

代码实现（C++）

#include <iostream>
#include <climits>
#include <cstring>
#include <cstdio>
#include <bitset>
#include <vector>

#define	MAXW	10

using namespace std;

bitset<MAXW + 1>			g[MAXW + 1];
char						dp_w[MAXW + 1][MAXW + 1];
vector<pair<char, char> >	cov;
vector<char>				to_cov[MAXW + 1][MAXW + 1];
bool						vis_cov[MAXW * MAXW];
bool						cp_vis_cov[MAXW * MAXW];

int		w, h;
int		hval;
int		bound;
int		stp;

inline int
min( int a, int b ) {
	
	return a < b ? a : b;
}

int
h_val(void) {
	
	int		i, j, k;
	int		lft;
	
	memcpy(cp_vis_cov, vis_cov, sizeof(vis_cov));
	
	lft = 0;
	for ( i = 1; i <= h; i++ )
		for ( j = 1; j <= w; j++ )
			if ( g[i][j] ) {
				
				for ( k = 0; k < to_cov[i][j].size(); k++ )
					if ( cp_vis_cov[ to_cov[i][j][k] ] )
						goto _h_val_CONT_;
				
				lft++;
				for ( k = 0; k < to_cov[i][j].size(); k++ )
					cp_vis_cov[ to_cov[i][j][k] ] = true;
				
				_h_val_CONT_:	continue;
			}
	
	return lft;
}

int
dfs( int x, int y ) {
	
	int		k;
	int		tmp_bound;
	int		ret_bound;
	
	if ( !hval ) return -1;
	if ( hval + stp > bound ) return hval + stp;
	
	if ( y > w ) { y = 1; x++; }
	
	if ( !g[x][y] ) return dfs( x, y + 1 );
	for ( k = 0; k < to_cov[x][y].size(); k++ )
		if ( vis_cov[ to_cov[x][y][k] ] )
			return dfs( x, y + 1 );
	
	ret_bound = INT_MAX;
	for ( k = 0; k < to_cov[x][y].size(); k++ ) {
		
		vis_cov[ to_cov[x][y][k] ] = true; hval = h_val();
		stp++;
		if ( ( tmp_bound = dfs( x, y + 1 ) ) == -1 ) return -1;
		stp--;
		vis_cov[ to_cov[x][y][k] ] = false;
		
		ret_bound = min( ret_bound, tmp_bound );
	}
	
	return ret_bound;
}

int
main() {
	
	int		i, j, k;
	int		x, y;
	int		bit;
	
	while ( scanf("%d%d", &w, &h), w ) {
		
		memset(vis_cov, 0, sizeof(vis_cov));
		
		for ( i = 1; i <= h; i++ )
			for ( j = 1; j <= w; j++ ) {
				
				scanf("%d", &bit);
				g[i][j] = bit;
			}
		
		cov.clear();
		for ( i = 1; i <= w; i++ ) dp_w[h][i] = g[h][i];
		for ( i = 1; i <= h; i++ ) dp_w[i][w] = g[i][w];
		for ( i = h - 1; i > 0; i-- )
			for ( j = w - 1; j > 0; j-- )
				dp_w[i][j] = !g[i][j] ? 0 :
				1 + min( min( dp_w[i + 1][j], dp_w[i][j + 1] ),
					dp_w[i + 1][j + 1] );
		
		for ( i = 1; i <= h; i++ )
			for ( j = 1; j <= w; j++ )
				if ( g[i][j] ) {
					
					for ( x = 1; x <= i; x++ )
						for ( y = 1; y <= j; y++ ) {
							
							if ( x == i && y == j ) continue;
							if ( x + dp_w[x][y] >= i + dp_w[i][j] &&
								y + dp_w[x][y] >= j + dp_w[i][j] )
								goto _CONT_;
						}
					
					cov.push_back(make_pair(i, j));
					_CONT_:				continue;
				}
		
		for ( i = 1; i <= h; i++ )
			for ( j = 1; j <= w; j++ )
				if ( g[i][j] ) {
					
					to_cov[i][j].clear();
					for ( k = 0; k < cov.size(); k++ ) {
						
						x = cov[k].first;
						y = cov[k].second;
						
						if ( x <= i && y <= j &&
							x + dp_w[x][y] > i &&
							y + dp_w[x][y] > j )
							to_cov[i][j].push_back(k);
					}
				}
		
		for ( stp = 0, bound = 0, hval = h_val(); bound != -1; bound = dfs( 1, 1 ) );
		printf("%d\n", stp);
	}
	
	return 0;
}

复杂度分析

• 时间复杂度：最坏情况下为 $O((WH)^k)$，其中 $k$ 是地毯数量，但由于 $W, H \leq 10$ 且剪枝优化，实际运行较快。
• 空间复杂度：$O(WH)$，用于存储覆盖状态。

示例解释

• 样例1：
  输入：

  4 3
  0 1 1 1
  1 1 1 1
  1 1 1 1
  

  最少需要 $2$ 块地毯（如 $3 \times 3$ 和 $1 \times 1$）。

• 样例2：
  输入：

  8 5
  0 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1
  1 1 1 0 1 1 1 1
  0 1 1 1 0 1 1 1
  

  最少需要 $6$ 块地毯。