铺瓷砖Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
给定一个大小为 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, m <= 13
# 思路
暴搜剪枝就行, 初始解使用每次填充最小边长的方法构造
# 解法
class Solution {
private int res;
private boolean visited[][];
private void _cal(int n, int m) {
//如果没有缓存则需要计算
//从左上角的点开始枚举
int max = Math.min(n, m);
for (int len = max; len > 0; len--) {
//标记状态
_mark(0, 0, len, len);
_dfs(n, m, 1);
_unmark(0, 0, len, len);
}
}
private void _mark(int x, int y, int n, int m) {
for (int i = y; i < y + n; i++) {
for (int j = x; j < x + m; j++) {
visited[i][j] = true;
}
}
}
private void _unmark(int x, int y, int n, int m) {
for (int i = y; i < y + n; i++) {
for (int j = x; j < x + m; j++) {
visited[i][j] = false;
}
}
}
private void _dfs(int n, int m, int depth) {
//如果当前方案能够得到的解不可能比当前找到的最优解更小 就不用精确计算到底还需要多少了，返回1就比最优解差了
if (depth >= res) return;
//找到一个空白点
int posX = 0;
int posY = 0;
boolean found = false;
for (int i = 0; i < n && found == false; i++) {
for (int j = 0; j < m; j++) {
if (visited[i][j] == false) {
posX = j;
posY = i;
found = true;
break;
}
}
}
//如果找不到空地
if (found == false) {
res = depth;
return;
}
//尝试在新的空白点放置各种大小的矩形
int max = Math.min(m - posX, n - posY);
for (int len = max; len > 0; len--) {
//判断是否能够放下
if (_canPlace(posX, posY, len)) {
//尝试计算
_mark(posX, posY, len, len);
_dfs(n, m, depth + 1);
_unmark(posX, posY, len, len);
}
}
}
private boolean _canPlace(int x, int y, int len) {
for (int i = x; i < x + len; i++) {
for (int j = y; j < y + len; j++) {
if (visited[j][i]) return false;
}
}
return true;
}
public int tilingRectangle(int n, int m) {
//因为输入规模比较小 暴力搜索剪枝即可
if (n == m) return 1;
visited = new boolean[n][];
//visited[y][x] 标识(y,x)位置1*1的空地是否被铺了瓷砖 其中 y=[0,n] x =[0, m]
for (int i = 0; i < n; i++) visited[i] = new boolean[m];
int t = Math.min(n, m);
//使用辗转相除的办法可以构造一个解 最优解肯定是小于等于该解的
//相当于每次都填充一个最小边长的矩形
int tn = n;
int tm = m;
res = 0;
while (tn > 0 && tm > 0) {
//始终另 tn > tm
if (tn < tm) {
int tt = tn;
tn = tm;
tm = tt;
}
//填充 tn/tm 个长度为tm的正方形
res += tn / tm;
tn -= tn / tm * tm;
}
_cal(n, m);
return res;
}
}
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
# 总结
- 分析出几种情况，然后分别对各个情况实现
