aboutsummaryrefslogtreecommitdiff
path: root/other/rectangle_fewest_squares.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/rectangle_fewest_squares.cpp')
-rw-r--r--other/rectangle_fewest_squares.cpp51
1 files changed, 0 insertions, 51 deletions
diff --git a/other/rectangle_fewest_squares.cpp b/other/rectangle_fewest_squares.cpp
deleted file mode 100644
index ef56533..0000000
--- a/other/rectangle_fewest_squares.cpp
+++ /dev/null
@@ -1,51 +0,0 @@
-#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);
-}