blob: ef56533a3e2f5b04ac11cc0d0594dc3aba12736a (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#include "leetcode.h"
class Solution {
public:
int maxDepth = 0;
int tilingRectangle(int n, int m) {
if (n > m)
swap(n, m);
vector<int> s;
for (int i = 0; i < n; i++)
s.push_back(m);
maxDepth = max(n, m);
dfs(s, 0);
return maxDepth;
}
private:
typedef long long key;
unordered_map<key, int> dp;
key hash(vector<int> &j) {
key r = 0;
for (int n : j)
r = (r << 4LL) + n;
return r;
}
void dfs(vector<int> j, int depth) {
key h = hash(j);
if (h == 0) {
maxDepth = min(maxDepth, depth);
return;
}
if (depth >= maxDepth || dp.count(h))
return;
auto topLeft = max_element(j.begin(), j.end());
int width = 1;
for (auto top = topLeft + 1; top != j.end() && *top == *topLeft; top++)
width++;
for (int w = min(width, *topLeft); w > 0; w--) {
for (int i = 0; i < w; i++)
*(topLeft + i) -= w;
dfs(j, depth + 1);
for (int i = 0; i < w; i++)
*(topLeft + i) += w;
}
}
};
int main() {
Solution obj;
cout << obj.tilingRectangle(2, 3);
}
|