本文共 2505 字，大约阅读时间需要 8 分钟。

你有一块棋盘，棋盘上有一些格子已经坏掉了。你还有无穷块大小为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. 1 <= n <= 8
2. 1 <= m <= 8
3. 0 <= b <= n * m

解题思路

首先可以想到通过dfs来做这个问题。对于每个位置来说只有三种情况，横着摆放多米诺骨牌、竖着摆放多米诺骨牌和不摆放多米诺骨牌。

class Solution:    def domino(self, n: int, m: int, broken: List[List[int]]) -> int:        g = [[0]*m for _ in range(n)]        for i, j in broken:            g[i][j] = 1        def dfs(x, y):            res1, res2 = 0, 0            if x >= n:                return 0            if y >= m:                return dfs(x + 1, 0)            if g[x][y]:                return dfs(x, y + 1)            #横            if y + 1 < m and g[x][y + 1] == 0:                g[x][y] = g[x][y + 1] = 1                res1 = dfs(x, y + 2) + 1                g[x][y] = g[x][y + 1] = 0            #竖            if x + 1 < n and g[x + 1][y] == 0:                g[x][y] = g[x + 1][y] = 1                res2 = dfs(x, y + 1) + 1                g[x][y] = g[x + 1][y] = 0            #不放            if res1 == 0 and res2 == 0:                return dfs(x, y + 2)            return max(res1, res2)                      return dfs(0, 0)

这个问题也可以通过二分图最大匹配来做。为什么呢？我们实际上可以将棋盘看成是国际象棋的棋盘（黑白相间，相当于两个集合），而多米诺骨牌需要跨越相邻的两个黑白区域（相当于二分图的一条边），那么计算多米诺骨牌可以最多摆放的个数，实际上就是求解二分图的最大匹配。关于二分图可以查看

构建二分图的时候采用的是邻接表的方式，由于二分图中是一个集合的点指向另外一个集合，这里采用白色点指向黑色点。

class Solution:    def domino(self, n: int, m: int, broken: List[List[int]]) -> int:        g = collections.defaultdict(list)        brk = set(x * m + y for x, y in broken)        for i in range(n):            for j in range(m):                if i * m + j in brk:                     continue                t = (i + j) & 1 # 偶数白，奇数黑                if i < n - 1 and (i + 1) * m + j not in brk:                    g[(i + t) * m + j].append((i + 1 - t) * m + j)                if j < m - 1 and i * m + j + 1 not in brk:                    g[i * m + j + t].append(i * m + j + 1 - t)                            match = {
   }        def find(x, st):            for y in g[x]:                if y not in st:                    st.add(y)                    if y not in match or find(match[y], st):                        match[y] = x                        return True            return False        return sum(find(x, set()) for x in g)

如有问题，希望大家指出！！！

转载地址：https://coordinate.blog.csdn.net/article/details/102522558 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！