铺瓷砖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

# 总结

分析出几种情况，然后分别对各个情况实现

#Java