本文涉及知識點
回溯
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++**實現。
