aboutsummaryrefslogtreecommitdiff
path: root/rectangle_fewest_squares.cpp
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);
}