(匈牙利算法) LCP 04. 覆盖

题目传送门

匈牙利算法模板题

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

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

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

示例 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 <= n <= 8
1 <= m <= 8
0 <= b <= n * m

解答

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

class Solution {
public:
    int h[N], e[N*N], ne[N*N], idx = 0;
    int match[N];
    bool st[N];

    void init() {
        memset(h, -1, sizeof h);
        memset(e, 0, sizeof e);
        memset(ne, 0, sizeof ne);
        idx = 0;
        memset(match, 0, sizeof match);
    }

    void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    bool find(int x) {      // 匈牙利算法找最大匹配
        for(int i = h[x]; i != -1; i = ne[i]) {
            int j = e[i];
            if(!st[j]) {
                st[j] = true;
                if(match[j] == 0 || find(match[j])) {
                    match[j] = x;
                    return true;
                }
            }
        }
        return false;
    }

    int domino(int n, int m, vector<vector<int>>& broken) {
        init();
        unordered_set<int> hashtable;
        vector<int> left_node;
        for(auto v : broken) {
            int x = v[0] + 1, y = v[1] + 1;
            int order = (x - 1) * m + y;
            hashtable.insert(order);
        }
        for(int i = 1; i<=n; i++) {
            for(int j = 1; j<=m; j++) {
                if((i % 2 && j % 2) || (i % 2 == 0 && j % 2 == 0)) { // 奇数行，加奇数位; 偶数行，加偶数位
                    int order = (i - 1) * m + j;
                    if(hashtable.find(order) != hashtable.end()) continue;
                    left_node.push_back(order);
                    for(int k = 0; k <4; k++) {
                        int ii = i + dx[k], jj = j + dy[k];
                        if(ii<1 || ii>=n+1 || jj<1 || jj>=m+1) continue;
                        int next_order = (ii-1)*m + jj;
                        if(hashtable.find(next_order) != hashtable.end()) continue;
                        add(order, next_order);
                    }
                }
            }
        }
        int ans = 0;
        for(int i = 0; i<left_node.size(); i++) {
            memset(st, false, sizeof st);
            if(find(left_node[i]))
                ans++;
        }
        return ans;
    }
};