怎样自己做淘宝客网站模板网站建设开发
本文涉及知识点
回溯
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
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
|---|
| 《喜缺全书算法册》以原理、正确性证明、总结为主。 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
