题目描述
给定一个 n
x m
的矩形,找到最少需要用到多少块正方形瓷砖将其铺满。
样例
输入:n = 2, m = 3
输出:3
解释:3 块正方形就可以铺满。
2 块 1x1 的正方形
1 块 2x2 的正方形
输入:n = 5, m = 8
输出:5
输入:n = 11, m = 13
输出:6
限制
1 <= n <= 13
1 <= m <= 13
算法
(递归回溯)
- 按位置进行递归回溯。如果当前位置已经被铺了,递归到下一层。否则尝试不同尺寸的正方形。
- 到最后一个位置时可以更新答案。可以用位运算来加速。
C++ 代码
class Solution {
public:
void solve(int x, int y, int n, int m, int tot, int& ans, vector<int>& filled) {
if (tot >= ans) return;
if (y == m) { x++; y = 0; }
if (x == n) { ans = tot; return; }
if ((filled[x] >> y) & 1) {
solve(x, y + 1, n, m, tot, ans, filled);
} else {
int r = 0, c = 0;
for (int i = x; i < n; i++) {
if ((filled[i] >> y) & 1) break;
r++;
}
for (int j = y; j < m; j++) {
if ((filled[x] >> j) & 1) break;
c++;
}
int t = min(r, c);
for (int s = 1; s <= t; s++) {
for (int i = 0; i < s; i++) {
filled[x + s - 1] |= 1 << (y + i);
filled[x + i] |= 1 << (y + s - 1);
}
solve(x, y + 1, n, m, tot + 1, ans, filled);
}
for (int i = x; i < x + t; i++)
for (int j = y; j < y + t; j++)
filled[i] ^= 1 << j;
}
}
int tilingRectangle(int n, int m) {
int ans = n * m;
vector<int> filled(n, 0);
solve(0, 0, n, m, 0, ans, filled);
return ans;
}
};
第二个递归调用 solve(x, y + 1, n, m, tot + 1, ans, filled);
可以改成 solve(x, y + s, n, m, tot + 1, ans, filled);
DFS搜索+楼下hxd的贪心优化
你好,带点贪心是不是更好呢,我跑了一下,快了不少。
class Solution {
public:
void solve(int x, int y, int n, int m, int tot, int& ans, vector[HTML_REMOVED]& filled) {
if (tot >= ans) return;
if (y == m) { x++; y = 0;}
if (x == n) { ans = tot; return; }
};
带点贪心得剪枝是可以的,但一定要保证正确性。
alternative 实现。
昨天leetcode周赛第四题,太牛了,这测试用例怎么搬过来的
和这题AcWing 291. 蒙德里安的梦想像吗
那题因为题目属性1x2的地板 所以能用到状压和二分图最大匹配 这题没有那个性质
这么快就出题解了,给大佬跪了!