算法疑难杂症

LCP04-覆盖

字数统计: 1.9k字   |   阅读时长: 8分
, , ,

摘要: LCP04，状态压缩DP和二分图匹配两种解法

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

今天我们来看一个比较难的图论题，力扣 LCP04。有状态压缩 DP 和二分图最大权匹配两种解法。之前还有另一个题 【DP难题】力扣1595-连通两组点的最小成本 也是状态压缩 DP 和二分图最大权匹配两种解法。可以对比着看。

题目

你有一块棋盘，棋盘上有一些格子已经坏掉了。你还有无穷块大小为1 * 2的多米诺骨牌，你想把这些骨牌不重叠地覆盖在完好的格子上，请找出你最多能在棋盘上放多少块骨牌？这些骨牌可以横着或者竖着放。

输入：n, m代表棋盘的大小；broken是一个b * 2的二维数组，其中每个元素代表棋盘上每一个坏掉的格子的位置。

输出：一个整数，代表最多能在棋盘上放的骨牌数。

1
2
3
4
限制：
1 <= n <= 8
1 <= m <= 8
0 <= b <= n * m

示例 1：
输入：n = 2, m = 3, broken = [[1, 0], [1, 1]]
输出：2
解释：我们最多可以放两块骨牌：[[0, 0], [0, 1]]以及[[0, 2], [1, 2]]。（见下图）

示例 2：
输入：n = 3, m = 3, broken = []
输出：4
解释：下图是其中一种可行的摆放方式

题解

算法1: 二分图匹配

二分图匹配有两个要点

  • 节点能分成独立的两个集合，每个集合内部有 0 条边。
  • 每个节点只能与 1 条匹配的边相连

把实际问题抽象成二分图匹配问题时，要寻找具有以上两条性质的对象。

本题中，任意两张骨牌不重叠，也就是每个格子只能被一张骨牌覆盖，与要点 2 对应。而骨牌大小是 1 * 2，与要点 1 对应。因此，我们可以把棋盘上未被禁止的各自作为节点，骨牌作为无向边。

建图之后，用匈牙利算法进行二分图最大匹配。

在文章 二分图匹配-最大匹配 中，有关于匈牙利算法的详细阐述。

代码(C++)

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
class Solution {
public:
    int domino(int n, int m, vector<vector<int>>& broken) {
        int n_broken = broken.size();
        vector<vector<int>> g(n * m);
        unordered_set<int> setting;
        for(const vector<int>& b: broken)
            setting.insert(key(b[0], b[1], m));
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
            {
                int u = key(i, j, m);
                if(setting.count(u) > 0)
                    continue;
                for(int d = 0; d < 4; ++d)
                {
                    int x = i + dx[d];
                    int y = j + dy[d];
                    if(x < 0 || x >= n || y < 0 || y >= m)
                        continue;
                    int v = key(x, y, m);
                    if(setting.count(v) > 0)
                        continue;
                    g[u].push_back(v);
                }
            }
        int ans = 0;
        vector<bool> visited;
        vector<int> match(n * m, -1);
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
            {
                int u = key(i, j, m);
                if(setting.count(u) > 0)
                    continue;
                visited.assign(n * m, false);
                visited[u] = true;
                if(dfs(u, g, visited, match))
                    ++ans;
            }
        return ans / 2;
    }

    bool dfs(int u, const vector<vector<int>>& g, vector<bool>& visited, vector<int>& match)
    {
        for(int v: g[u])
        {
            if(visited[v])
                continue;
            visited[v] = true;
            if(match[v] == -1 || dfs(match[v], g, visited, match))
            {
                match[v] = u;
                return true;
            }
        }
        return false;
    }

    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};

    int key(int x, int y, int m)
    {
        return x * m + y;
    }
};

算法2: 状态压缩DP

在文章 状态压缩DP 中，我们用状态压缩 DP 解决过类似的问题，本题有两个变化：

  1. 多了障碍点
  2. 问有多少种铺满方案改成了最多放多少骨牌

考虑以某一行为界，将棋盘分成上下两部分。

假设前 i - 1 行已经摆放好，考虑第 i 行的各个位置，如果某个位置(第 j 列)的前一行是竖着的骨牌的上半部分，则该部分必须补全该骨牌而无法放新骨牌，如果该位置为障碍点，则该位置也无法放新骨牌。其余情况则该位置可以放置新骨牌。

也就是说，当 (i, j) 位置出现以下两种情况之一，则该位置无法放置新骨牌

  1. (i, j) 位置是障碍点
  2. (i - 1, j) 放置了一块竖着的骨牌

因此，可以把行号作为 DP 的阶段，把上半部分不断向下扩展，直至确定整个棋盘。

为了描述第 i 行的可放新骨牌的位置的详细形态，用一个 m 位二进制数，其中第 j 位为 0 表示 (i, j) 不能放置新骨牌；为 1 表示可以放置新骨牌。

当第 i 行的状态为 s 的时候，考察所有可以放骨牌的位置(s >> j & 1 为 1 的位置)，有三种可能的选择

  1. 不放置
  2. 竖着放置，此时会影响到下一行
  3. 横着放置

枚举所有可竖着放置位置组成的集合的子集，对子集中的位置竖着放置，剩余位置尽可能多地横着放置，此时第 i 行就放置完了，即可将阶段从 i 推进到 i + 1，考察第 i + 1 行的状态。

完整算法如下

1
2
3
4
5
6
7
8
9
10
11
12
状态定义
dp[i][s] := 表示第 i 行的形态为 s 的时候，第 i 行到第 n 行(最后一行下面假想的一行)的方案总数

答案
dp[0][(~b[0]) & mask]

初始化
dp[n][s] = 0

状态转移
dp[i][s] = max(竖着放置的数目 + 横着放置的数目 + dp[i + 1][(~(t | b[i + 1])) & mask])
其中 t 是 s 的子集，且 (t & b[i + 1]) = 0

其中:

  • b[i] 表示第 i 行障碍点的情况，(b[i] >> j & 1) 为 1 表示 (i, j) 为障碍点。
  • mask 为 (1 << m) - 1

dp[n][s] 表示的是棋盘最后一行下面假想的一行，这一行视为全都是障碍点，这样处理比较好写。

代码(C++)

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
class Solution {
public:
    int domino(int n, int m, vector<vector<int>>& broken) {
        mask = (1 << m) - 1;
        vector<int> b(n + 1, 0);
        b[n] = mask;
        for(const vector<int>& broken_point: broken)
        {
            int i = broken_point[0];
            int j = broken_point[1];
            b[i] |= (1 << j);
        }
        vector<vector<int>> dp(n + 1, vector<int>(1 << m, -1));
        for(int s = 0; s < (1 << m); ++s)
            dp[n][s] = 0;
        return solve(0, (~b[0]) & mask, b, dp);
    }

    int mask;

    int solve(int i, int s, const vector<int>& b, vector<vector<int>>& dp)
    {
        if(dp[i][s] != -1)
            return dp[i][s];
        dp[i][s] = 0;
        for(int t = s; ; t = (t - 1) & s)
        {
            if((t & b[i + 1]) != 0)
                continue;
            int n1 = check1(t); // 竖着放的个数
            int n2 = check2(s & (~t)); // 横着放的个数
            dp[i][s] = max(dp[i][s], n1 + n2 + solve(i + 1, (~(t | b[i + 1])) & mask, b, dp));
            if(t == 0)
                break;
        }
        return dp[i][s];
    }

    int check2(int x)
    {
        // x 中长度为 2 的连续 1 的个数
        int n = 0;
        while(x > 0)
        {
            while(x > 0 && (x & 1) == 0)
                x >>= 1;
            x >>= 1;
            if((x & 1) == 1)
            {
                x >>= 1;
                ++n;
            }
        }
        return n;
    }

    int check1(int x)
    {
        // x 中 1 的个数
        int n = 0;
        while(x > 0)
        {
            if((x & 1) == 1)
                ++n;
            x >>= 1;
        }
        return n;
    }
};
Share