ให้สี่เหลี่ยมผืนผ้าขนาด n x m หาจำนวนสี่เหลี่ยมจัตุรัสขนาดจำนวนเต็มที่น้อยที่สุดที่สามารถปูครอบคลุมสี่เหลี่ยมผืนผ้าได้
เช่น n=2, m=3 เอาต์พุต = 3 (ต้องใช้ 3 ชิ้น)
วิธีแก้ − ใช้ DFS + Backtracking พร้อม Memoization ลองวางสี่เหลี่ยมจัตุรัสขนาดต่างๆ จากมุมที่ว่างอยู่ต่ำสุด
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
map<int, int> s;
int res = INT_MAX;
void dfs(int n, int m, vector<int> h, int cnt){
if (cnt >= res) return;
bool isFull = true;
int pos = -1, minH = INT_MAX;
for (int i = 1; i <= n; i++) {
if (h[i] < m) isFull = false;
if (h[i] < minH) { minH = h[i]; pos = i; }
}
if (isFull) { res = min(res, cnt); return; }
long key = 0, base = m + 1;
for (int i = 1; i <= n; i++) { key += h[i] * base; base *= m + 1; }
if (s.find(key) != s.end() && s[key] <= cnt) return;
s[key] = cnt;
int end = pos;
while (end + 1 <= n && h[end + 1] == h[pos] && (end + 1 - pos + 1 + minH) <= m) end++;
for (int j = end; j >= pos; j--) {
int curH = j - pos + 1;
vector<int> next(n + 1);
for (int i = 1; i <= n; i++) next[i] = h[i];
for (int k = pos; k <= j; k++) next[k] += curH;
dfs(n, m, next, cnt + 1);
}
}
int tilingRectangle(int n, int m){
if (n == m) return 1;
if (n > m) swap(n, m);
vector<int> h(n + 1);
dfs(n, m, h, 0);
return res;
}
};
main(){
Solution ob;
cout << (ob.tilingRectangle(2, 3));
}
อินพุต
2,3
เอาต์พุต
3
