1240. 铺瓷砖
你是一位施工队的工长，根据设计师的要求准备为一套设计风格独特的房子进行室内装修。
房子的客厅大小为 n x m，为保持极简的风格，需要使用尽可能少的 正方形 瓷砖来铺盖地面。
假设正方形瓷砖的规格不限，边长都是整数。
请你帮设计师计算一下，最少需要用到多少块方形瓷砖？
示例 1：
输入：n = 2, m = 3 输出：3解释：3块地砖就可以铺满卧室。2块1x1 地砖1块2x2 地砖
示例 2：
输入：n = 5, m = 8 输出：5
示例 3：
输入：n = 11, m = 13 输出：6
提示：
1 <= n <= 131 <= m <= 13原站题解
javascript 解法, 执行用时: 76 ms, 内存消耗: 41.9 MB, 提交时间: 2023-06-08 09:33:47
/**
* @param {number} n
* @param {number} m
* @return {number}
*/
var tilingRectangle = function(n, m) {
let ans = Math.max(n, m);
const rect = new Array(n).fill(0).map(() => new Array(m).fill(false));
const dfs = (x, y, rect, cnt) => {
const n = rect.length, m = rect[0].length;
if (cnt >= ans) {
return;
}
if (x >= n) {
ans = cnt;
return;
}
/* 检测下一行 */
if (y >= m) {
dfs(x + 1, 0, rect, cnt);
return;
}
/* 如当前已经被覆盖，则直接尝试下一个位置 */
if (rect[x][y]) {
dfs(x, y + 1, rect, cnt);
return;
}
for (let k = Math.min(n - x, m - y); k >= 1 && isAvailable(rect, x, y, k); k--) {
/* 将长度为 k 的正方形区域标记覆盖 */
fillUp(rect, x, y, k, true);
/* 跳过 k 个位置开始检测 */
dfs(x, y + k, rect, cnt + 1);
fillUp(rect, x, y, k, false);
}
}
dfs(0, 0, rect, 0);
return ans;
}
const isAvailable = (rect, x, y, k) => {
for (let i = 0; i < k; i++) {
for (let j = 0; j < k; j++) {
if (rect[x + i][y + j]) {
return false;
}
}
}
return true;
}
const fillUp = (rect, x, y, k, val) => {
for (let i = 0; i < k; i++){
for (let j = 0; j < k; j++) {
rect[x + i][y + j] = val;
}
}
};
python3 解法, 执行用时: 156 ms, 内存消耗: 16.3 MB, 提交时间: 2023-06-08 09:33:26
class Solution:
def tilingRectangle(self, n: int, m: int) -> int:
def dfs(x: int, y: int, cnt: int) -> None:
nonlocal ans
if cnt >= ans:
return
if x >= n:
ans = cnt
return
# 检测下一行
if y >= m:
dfs(x + 1, 0, cnt)
return
# 如当前已经被覆盖，则直接尝试下一个位置
if rect[x][y]:
dfs(x, y + 1, cnt)
return
k = min(n - x, m - y)
while k >= 1 and isAvailable(x, y, k):
fillUp(x, y, k, True)
# 跳过 k 个位置开始检测
dfs(x, y + k, cnt + 1)
fillUp(x, y, k, False)
k -= 1
def isAvailable(x: int, y: int, k: int) -> bool:
for i in range(k):
for j in range(k):
if rect[x + i][y + j] == True:
return False
return True
def fillUp(x: int, y: int, k: int, val: bool) -> None:
for i in range(k):
for j in range(k):
rect[x + i][y + j] = val
ans = max(n, m)
rect = [[False] * m for _ in range(n)]
dfs(0, 0, 0)
return ans
golang 解法, 执行用时: 4 ms, 内存消耗: 1.9 MB, 提交时间: 2023-06-08 09:33:12
func max(a, b int) int { if a > b { return a }; return b }
func min(a, b int) int { if a < b { return a }; return b }
func tilingRectangle(n int, m int) int {
ans := max(n, m)
rect := make([][]bool, n)
for i := 0; i < n; i++ {
rect[i] = make([]bool, m)
}
isAvailable := func(x, y, k int) bool {
for i := 0; i < k; i++ {
for j := 0; j < k; j++ {
if rect[x + i][y + j] {
return false
}
}
}
return true
}
fillUp := func(x, y, k int, val bool) {
for i := 0; i < k; i++ {
for j := 0; j < k; j++ {
rect[x + i][y + j] = val
}
}
}
var dfs func(int, int, int)
dfs = func(x, y, cnt int) {
if cnt >= ans {
return
}
if x >= n {
ans = cnt
return
}
// 检测下一行
if y >= m {
dfs(x + 1, 0, cnt)
return
}
// 如当前已经被覆盖，则直接尝试下一个位置
if rect[x][y] {
dfs(x, y + 1, cnt)
return
}
for k := min(n - x, m - y); k >= 1 && isAvailable(x, y, k); k-- {
// 将长度为 k 的正方形区域标记覆盖
fillUp(x, y, k, true)
// 跳过 k 个位置开始检测
dfs(x, y + k, cnt + 1)
fillUp(x, y, k, false)
}
}
dfs(0, 0, 0)
return ans
}
golang 解法, 执行用时: 112 ms, 内存消耗: 1.9 MB, 提交时间: 2023-06-08 09:32:14
func tilingRectangle(n int, m int) int {
ans := n * m
filled := make([]int, n)
var dfs func(i, j, t int)
dfs = func(i, j, t int) {
if j == m {
i++
j = 0
}
if i == n {
ans = t
return
}
if filled[i]>>j&1 == 1 {
dfs(i, j+1, t)
} else if t+1 < ans {
var r, c int
for k := i; k < n; k++ {
if filled[k]>>j&1 == 1 {
break
}
r++
}
for k := j; k < m; k++ {
if filled[i]>>k&1 == 1 {
break
}
c++
}
mx := min(r, c)
for w := 1; w <= mx; w++ {
for k := 0; k < w; k++ {
filled[i+w-1] |= 1 << (j + k)
filled[i+k] |= 1 << (j + w - 1)
}
dfs(i, j+w, t+1)
}
for x := i; x < i+mx; x++ {
for y := j; y < j+mx; y++ {
filled[x] ^= 1 << y
}
}
}
}
dfs(0, 0, 0)
return ans
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
java 解法, 执行用时: 116 ms, 内存消耗: 38.1 MB, 提交时间: 2023-06-08 09:31:41
class Solution {
private int n;
private int m;
private int[] filled;
private int ans;
public int tilingRectangle(int n, int m) {
this.n = n;
this.m = m;
ans = n * m;
filled = new int[n];
dfs(0, 0, 0);
return ans;
}
private void dfs(int i, int j, int t) {
if (j == m) {
++i;
j = 0;
}
if (i == n) {
ans = t;
return;
}
if ((filled[i] >> j & 1) == 1) {
dfs(i, j + 1, t);
} else if (t + 1 < ans) {
int r = 0, c = 0;
for (int k = i; k < n; ++k) {
if ((filled[k] >> j & 1) == 1) {
break;
}
++r;
}
for (int k = j; k < m; ++k) {
if ((filled[i] >> k & 1) == 1) {
break;
}
++c;
}
int mx = Math.min(r, c);
for (int w = 1; w <= mx; ++w) {
for (int k = 0; k < w; ++k) {
filled[i + w - 1] |= 1 << (j + k);
filled[i + k] |= 1 << (j + w - 1);
}
dfs(i, j + w, t + 1);
}
for (int x = i; x < i + mx; ++x) {
for (int y = j; y < j + mx; ++y) {
filled[x] ^= 1 << y;
}
}
}
}
}
python3 解法, 执行用时: 5648 ms, 内存消耗: 16.3 MB, 提交时间: 2023-06-08 09:31:26
'''
递归回溯 + 状态压缩
我们可以按位置进行递归回溯，过程中我们用一个变量 t 记录当前使用的瓷砖数。
如果 j=m，即第 i 行已经被完全填充，则递归到下一行，即 (i+1,0)。
如果 i=n，则表示所有位置都已经被填充，我们更新答案并返回。
如果当前位置 (i,j) 已经被填充，则直接递归到下一个位置 (i,j+1)。
否则，我们枚举当前位置 (i,j) 可以填充的最大正方形的边长 w，
并将当前位置 (i,j) 到 (i+w−1,j+w−1) 的位置全部填充，
然后递归到下一个位置 (i,j+w)。在回溯时，我们需要将当前位置 (i,j) 到 (i+w−1,j+w−1) 的位置全部清空。
由于每个位置只有两种状态：填充或者未填充，因此我们可以使用一个整数来表示当前位置的状态。
我们使用一个长度为 n 的整数数组 filled，其中 filled[i] 表示第 i 行的状态。
如果 filled[i] 的第 j 位为 1，则表示第 i 行第 j 列已经被填充，否则表示未填充。
'''
class Solution:
def tilingRectangle(self, n: int, m: int) -> int:
def dfs(i: int, j: int, t: int):
nonlocal ans
if j == m:
i += 1
j = 0
if i == n:
ans = t
return
if filled[i] >> j & 1:
dfs(i, j + 1, t)
elif t + 1 < ans:
r = c = 0
for k in range(i, n):
if filled[k] >> j & 1:
break
r += 1
for k in range(j, m):
if filled[i] >> k & 1:
break
c += 1
mx = r if r < c else c
for w in range(1, mx + 1):
for k in range(w):
filled[i + w - 1] |= 1 << (j + k)
filled[i + k] |= 1 << (j + w - 1)
dfs(i, j + w, t + 1)
for x in range(i, i + mx):
for y in range(j, j + mx):
filled[x] ^= 1 << y
ans = n * m
filled = [0] * n
dfs(0, 0, 0)
return ans