Giả sử chúng ta có một hình chữ nhật kích thước n x m. Chúng ta phải tìm số lượng tối thiểu các đối tượng hình vuông có cạnh nguyên có thể đắp đầy hình chữ nhật.
Vì vậy, nếu đầu vào giống như n = 2 và m = 3,
thì đầu ra sẽ là 3, vì chúng ta cần ba khối.
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau −
Định nghĩa một map m
res := inf
Định nghĩa hàm dfs(), nhận n, m, mảng h, cnt,
nếu cnt >= res, thì −
trả về
isFull := true
pos := -1, minH := inf
for khởi tạo i := 1, khi i <= n, cập nhật (tăng i lên 1), thực hiện −
nếu h[i] < m, thì −
isFull := false
nếu h[i] < minH, thì −
minH := h[i]
pos := i
nếu isFull khác 0, thì −
res := min của res và cnt
trả về
key := 0
base := m + 1
for khởi tạo i := 1, khi i <= n, cập nhật (tăng i lên 1), thực hiện −
key := key + h[i] * base
base := base * (m + 1)
nếu key có trong s và s[key] <= cnt, thì −
trả về
s[key] := cnt
end := pos
khi (end + 1 <= n và h[end + 1] bằng h[pos] và (end + 1 - pos + 1 + minH)
<= m), thực hiện −
(tăng end lên 1)
for khởi tạo j := end, khi j >= pos, cập nhật (giảm j xuống 1), thực hiện −
curH := j - pos + 1
Định nghĩa mảng next kích thước n + 1
for khởi tạo i := 1, khi i <= n, cập nhật (tăng i lên 1), thực hiện −
next[i] := h[i]
for khởi tạo k := pos, khi k <= j, cập nhật (tăng k lên 1), thực hiện −
next[k] := next[k] + curH
dfs(n, m, next, cnt + 1)
Từ phương thức main thực hiện như sau −
nếu n bằng m, thì −
trả về 1
nếu n > m, thì
hoán đổi(n, m)
Định nghĩa mảng h kích thước n + 1
dfs(n, m, h, 0)
trả về res
Hãy xem triển khai sau để hiểu rõ hơn −
Ví dụ
#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; long 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)); } Đầu vào
2,3
Đầu ra
3