算法leetcode

【搜索难题】力扣1240-铺瓷砖

字数统计: 1.1k字   |   阅读时长: 5分
,

摘要: 应用了最优性剪枝和搜索顺序

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文看一个搜索题，主要的难点在于需要应用最优性剪枝，以及改变搜索顺序的优化方法。

$1 题目

1240. 铺瓷砖

你是一位施工队的工长，根据设计师的要求准备为一套设计风格独特的房子进行室内装修。

房子的客厅大小为 n x m，为保持极简的风格，需要使用尽可能少的 正方形 瓷砖来铺盖地面。

假设正方形瓷砖的规格不限，边长都是整数。

请你帮设计师计算一下，最少需要用到多少块方形瓷砖？

提示：

1
2
1 <= n <= 13
1 <= m <= 13

示例 1：
输入：n = 2, m = 3
输出：3
解释：3 块地砖就可以铺满卧室。
2 块 1x1 地砖
1 块 2x2 地砖

示例 2：
输入：n = 5, m = 8
输出：5

示例 3：
输入：n = 11, m = 13
输出：6

$2 题解

算法: 搜索

整个棋盘的铺砖情况是状态，m * n 个点共有 $2^{nm}$ 种。

初态是全都没有铺砖，终态是全都铺砖了。

从初态开始用 DFS 穷举搜索终态，每到达一个新状态，按顺序做下面几件事：

  • 检查是否到达终态 (check函数1)
    • 如果是，更新答案后返回
    • 如果否，返回第一个没有铺砖的点 p
  • 拿到 p 之后，枚举所有可行的正方形边长:(check函数2)
    • 将枚举到的正方形覆盖范围做标记，得到新状态 (set函数)
    • 搜索新状态
    • 将本轮的正方形标记接触(reset函数)

基础搜索

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 {
public:
    int tilingRectangle(int n, int m) {
        board = vector<vector<bool>>(n, vector<bool>(m, false));
        int ans = n * m;
        dfs(0, ans);
        return ans;
    }

private:
    vector<vector<bool>> board;

    void dfs(int cnt, int& ans)
    {
        int x = -2, y = -2;
        if(check(x, y))
        {
            ans = min(ans, cnt);
            return;
        }
        int n = board.size(), m = board[0].size();
        int len = 1;
        while(check(x, y, n, m, len))
        {
            set(x, y, len);
            dfs(cnt + 1, ans);
            reset(x, y, len);
            ++len;
        }
    }

    void reset(int i, int j, int len);
    void set(int i, int j, int len);
    bool check(int i, int j, int n, int m, int len);
    bool check(int& x, int& y);
};

最优性剪枝

进入新状态时，检查当前路径走过的步数，如果已经大于等于此前走到终态所用步数的最小值，从最优性角度讲没必要继续搜索了。

1
2
3
4
5
6
void dfs(int cnt, int& ans)
{
    if(cnt >= ans)
        return;
    ...
}

搜索顺序

将正方形边长的枚举顺序从大到小，使得尽早剪枝。

1
2
3
4
5
6
7
8
int len = min(n - x, m - y);
while(len >= 1 && check(x, y, n, m, len))
{
    set(x, y, len);
    dfs(cnt + 1, ans);
    reset(x, y, len);
    --len;
}

代码 (C++)

性能记录：

1
2
3
4
基础搜索： 6 * 7  550ms
剪枝： 13 * 13 1360ms
搜索顺序： 8 * 8 900ms
剪枝+搜索顺序： 17 * 23 1770ms
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
class Solution {
public:
    int tilingRectangle(int n, int m) {
        board = vector<vector<bool>>(n, vector<bool>(m, false));
        int ans = n * m;
        dfs(0, ans);
        return ans;
    }

private:
    vector<vector<bool>> board;

    void dfs(int cnt, int& ans)
    {
        if(cnt >= ans)
            return;
        int x = -2, y = -2;
        if(check(x, y))
        {
            ans = min(ans, cnt);
            return;
        }
        int n = board.size(), m = board[0].size();
        int len = min(n - x, m - y);
        while(len >= 1 && check(x, y, n, m, len))
        {
            set(x, y, len);
            dfs(cnt + 1, ans);
            reset(x, y, len);
            --len;
        }
    }

    void reset(int i, int j, int len)
    {
        for(int x = i; x < i + len; ++x)
            for(int y = j; y < j + len; ++y)
                board[x][y] = false;
    }

    void set(int i, int j, int len)
    {
        for(int x = i; x < i + len; ++x)
            for(int y = j; y < j + len; ++y)
                board[x][y] = true;
    }

    bool check(int i, int j, int n, int m, int len)
    {
        if(i + len > n || j + len > m)
            return false;
        for(int x = i; x < i + len; ++x)
            for(int y = j; y < j + len; ++y)
            {
                if(board[x][y])
                    return false;
            }
        return true;
    }

    bool check(int& x, int& y)
    {
        int n = board.size(), m = board[0].size();
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
                if(!board[i][j])
                {
                    x = i;
                    y = j;
                    return false;
                }
        return true;
    }
};
Share