题目描述
给定一个大小为 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
提示：
解法
方法一：递归回溯 + 状态压缩
我们可以按位置进行递归回溯，过程中我们用一个变量 $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$ 列已经被填充，否则表示未填充。
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 | 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
|
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
52
53
54
55
56 | 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;
}
}
}
}
}
|
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
52
53
54
55
56
57 | class Solution {
public:
int tilingRectangle(int n, int m) {
memset(filled, 0, sizeof(filled));
this->n = n;
this->m = m;
ans = n * m;
dfs(0, 0, 0);
return ans;
}
private:
int filled[13];
int n, m;
int ans;
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) {
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) {
break;
}
++r;
}
for (int k = j; k < m; ++k) {
if (filled[i] >> k & 1) {
break;
}
++c;
}
int mx = 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;
}
}
}
}
};
|
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 | 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
}
|
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 | function tilingRectangle(n: number, m: number): number {
let ans = n * m;
const filled: number[] = new Array(n).fill(0);
const dfs = (i: number, j: number, t: number) => {
if (j === m) {
++i;
j = 0;
}
if (i === n) {
ans = t;
return;
}
if ((filled[i] >> j) & 1) {
dfs(i, j + 1, t);
} else if (t + 1 < ans) {
let [r, c] = [0, 0];
for (let k = i; k < n; ++k) {
if ((filled[k] >> j) & 1) {
break;
}
++r;
}
for (let k = j; k < m; ++k) {
if ((filled[i] >> k) & 1) {
break;
}
++c;
}
const mx = Math.min(r, c);
for (let w = 1; w <= mx; ++w) {
for (let 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 (let x = i; x < i + mx; ++x) {
for (let y = j; y < j + mx; ++y) {
filled[x] ^= 1 << y;
}
}
}
};
dfs(0, 0, 0);
return ans;
}
|
方法二
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 | 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 = min(r, c)
for x in range(i, i + mx):
for y in range(j, j + mx):
filled[x] |= 1 << y
for w in range(mx, 0, -1):
dfs(i, j + w, t + 1)
for k in range(w):
filled[i + w - 1] ^= 1 << (j + k)
if k < w - 1:
filled[i + k] ^= 1 << (j + w - 1)
ans = n * m
filled = [0] * n
dfs(0, 0, 0)
return ans
|
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
52
53
54
55
56
57
58 | 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 x = i; x < i + mx; ++x) {
for (int y = j; y < j + mx; ++y) {
filled[x] |= 1 << y;
}
}
for (int w = mx; w > 0; --w) {
dfs(i, j + w, t + 1);
for (int k = 0; k < w; ++k) {
filled[i + w - 1] ^= 1 << (j + k);
if (k < w - 1) {
filled[i + k] ^= 1 << (j + w - 1);
}
}
}
}
}
}
|
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
52
53
54
55
56
57
58
59 | class Solution {
public:
int tilingRectangle(int n, int m) {
memset(filled, 0, sizeof(filled));
this->n = n;
this->m = m;
ans = n * m;
dfs(0, 0, 0);
return ans;
}
private:
int filled[13];
int n, m;
int ans;
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) {
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) {
break;
}
++r;
}
for (int k = j; k < m; ++k) {
if (filled[i] >> k & 1) {
break;
}
++c;
}
int mx = min(r, c);
for (int x = i; x < i + mx; ++x) {
for (int y = j; y < j + mx; ++y) {
filled[x] |= 1 << y;
}
}
for (int w = mx; w; --w) {
dfs(i, j + w, t + 1);
for (int k = 0; k < w; ++k) {
filled[i + w - 1] ^= 1 << (j + k);
if (k < w - 1) {
filled[i + k] ^= 1 << (j + w - 1);
}
}
}
}
}
};
|
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 | 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 x := i; x < i+mx; x++ {
for y := j; y < j+mx; y++ {
filled[x] |= 1 << y
}
}
for w := mx; w > 0; w-- {
dfs(i, j+w, t+1)
for k := 0; k < w; k++ {
filled[i+w-1] ^= 1 << (j + k)
if k < w-1 {
filled[i+k] ^= 1 << (j + w - 1)
}
}
}
}
}
dfs(0, 0, 0)
return ans
}
|
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 | function tilingRectangle(n: number, m: number): number {
let ans = n * m;
const filled: number[] = new Array(n).fill(0);
const dfs = (i: number, j: number, t: number) => {
if (j === m) {
++i;
j = 0;
}
if (i === n) {
ans = t;
return;
}
if ((filled[i] >> j) & 1) {
dfs(i, j + 1, t);
} else if (t + 1 < ans) {
let [r, c] = [0, 0];
for (let k = i; k < n; ++k) {
if ((filled[k] >> j) & 1) {
break;
}
++r;
}
for (let k = j; k < m; ++k) {
if ((filled[i] >> k) & 1) {
break;
}
++c;
}
const mx = Math.min(r, c);
for (let x = i; x < i + mx; ++x) {
for (let y = j; y < j + mx; ++y) {
filled[x] |= 1 << y;
}
}
for (let w = mx; w > 0; --w) {
dfs(i, j + w, t + 1);
for (let k = 0; k < w; ++k) {
filled[i + w - 1] ^= 1 << (j + k);
if (k < w - 1) {
filled[i + k] ^= 1 << (j + w - 1);
}
}
}
}
};
dfs(0, 0, 0);
return ans;
}
|