在百度做网站怎么做,装修素材图片都从什么网站找,免费下载网页模板,wordpress 主题 her本文涉及知识点
回溯
LeetCode1240. 铺瓷砖
你是一位施工队的工长#xff0c;根据设计师的要求准备为一套设计风格独特的房子进行室内装修。 房子的客厅大小为 n x m#xff0c;为保持极简的风格#xff0c;需要使用尽可能少的 正方形 瓷砖来铺盖地面。 假设正方形瓷砖的…本文涉及知识点
回溯
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,clen开始。如果clen m则r,c0。
回溯代码
核心代码
templateclass ELE,class ELE2
void MinSelf(ELE* seft, const ELE2 other)
{*seft min(*seft,(ELE) other);
}templateclass 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::functionvoid(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;}
};测试用例
templateclass T
void Assert(const vectorT v1, const vectorT v2)
{if (v1.size() ! v2.size()){assert(false);return;}for (int i 0; i v1.size(); i){assert(v1[i] v2[i]);}
}templateclass 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 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。