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, 51 insertions, 0 deletions
diff --git a/other/rectangle_fewest_squares.cpp b/other/rectangle_fewest_squares.cpp
new file mode 100644
index 0000000..ef56533
--- /dev/null
+++ b/other/rectangle_fewest_squares.cpp
@@ -0,0 +1,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);
+}