【回溯】1240. 铺瓷砖

本文涉及知识点

回溯

LeetCode1240. 铺瓷砖

你是一位施工队的工长，根据设计师的要求准备为一套设计风格独特的房子进行室内装修。
房子的客厅大小为 n x m，为保持极简的风格，需要使用尽可能少的正方形瓷砖来铺盖地面。
假设正方形瓷砖的规格不限，边长都是整数。
请你帮设计师计算一下，最少需要用到多少块方形瓷砖？
示例 1：
在这里插入图片描述

输入：n = 2, m = 3
输出：3
解释：3 块地砖就可以铺满卧室。
2 块 1x1 地砖
1 块 2x2 地砖
示例 2：
在这里插入图片描述

输入：n = 5, m = 8
输出：5
示例 3：

输入：n = 11, m = 13
输出：6
在这里插入图片描述

提示：

1 <= n <= 13
1 <= m <= 13

回溯

aHas[r][c] 记录第r行，第c列是否已经铺设瓷砖。
先行后列处理第一个没有铺设的单格，从大到小尝试铺设瓷砖。
回溯最后一个层次：所有单格都已经铺满瓷砖。回溯结束：使用的磁盘是否小于结果。
一层回溯：
GetNext获取下一个没有铺瓷砖的单元格格。
如果所有单格都铺了瓷砖，则本次回溯失败。
计算最大能铺maxLen的瓷砖。注意：右下可能已有瓷砖。2*2的瓷砖无法放下。
在这里插入图片描述

len = maxLen :1
将len所在单格铺上瓷砖
回溯下一层次
将len所在单格瓷砖取消

小技巧

如果cnt已经大于等于res，则直接返回。
r,c 不必从0,0开始，从r,c+len开始。如果c+len >= m，则r++,c=0。

回溯代码

核心代码

template<class ELE,class ELE2>
void MinSelf(ELE* seft, const ELE2& other)
{
	*seft = min(*seft,(ELE) other);
}

template<class ELE>
void MaxSelf(ELE* seft, const ELE& other)
{
	*seft = max(*seft, other);
}

class Solution {
public:
	int tilingRectangle(int n, int m) {
		bool vHas[13][13] = { false };
		int iRet = n * m;
		auto  GetNext = [&](int& r, int& c) {
			if (c >= m) {
				r++;
				c = 0;
			}
			if (r >= n) { return true; };
			if (!vHas[r][c]) { return true; }
			c++;
			return false;
		};
		std::function<void(int, int,int)> BackTrack = [&](int r, int c,int cnt) {
			if (cnt >= iRet) { return; }
			while (!GetNext(r, c));
			if (r >= n) {
				iRet = min(iRet, cnt);
				return;
			}
			int maxLen = min(n - r, m - c);
			for (int i = r; i < r + maxLen; i++) {
				for (int j = c; j < c + maxLen; j++) {
					if (vHas[i][j]) {
						MinSelf(&maxLen, i - r);
						MinSelf(&maxLen, j - c);
					}
				}
			}
			for (int len = maxLen; len > 0; len--) {
				for (int i = r; i < r + len; i++) {
					for (int j = c; j < c + len; j++) {
						vHas[i][j] = true;
					}
				}
				BackTrack(r, c + len, cnt + 1);
				for (int i = r; i < r + len; i++) {
					for (int j = c; j < c + len; j++) {
						vHas[i][j] = false;
					}
				}
			}			
		};	
		BackTrack(0, 0, 0);
		return iRet;
	}
};

测试用例

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		assert(v1[i] == v2[i]);
	}
}

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

int main()
{
	{
		Solution slu;
		auto res = slu.tilingRectangle(1, 1);
		Assert(1, res);
	}
	{
		Solution slu;
		auto res = slu.tilingRectangle(1, 2);
		Assert(2, res);
	}
	{
		Solution slu;		
		auto res = slu.tilingRectangle(2, 3);
		Assert(3, res);
	}
	{
		Solution slu;
		auto res = slu.tilingRectangle(5, 8);
		Assert(5, res);
	}
	{
		Solution slu;
		auto res = slu.tilingRectangle(11, 13);
		Assert(6, res);
	}	
}

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛