覆盖骨牌数问题-Python语言与人工智能入门-课程设计

** 覆盖骨牌数问题**

问题具体描述：

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

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

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

（Python语言与人工智能入门-课程设计的小作业）

具体代码如下：

from typing import List

class Solution(object):

    def domino(self,n, m, broken):
 
        dx = [0, 0, -1, 1]
        dy = [-1, 1, 0, 0]
        match = [-1] * n * m

        #存储匹配的时候用id比较方便，寻找邻点使用坐标系方便
        pos2id = lambda y, x:y * m + x
        id2pos = lambda id:[id // m, id % m]

        #匈牙利求解最大匹配数
        def edmon_match(now_id):
            pos = id2pos(now_id)
            if vis[now_id]:
                return 0
            vis[now_id] = 1

            for i in range(4):
                new = [pos[0] + dy[i], pos[1] + dx[i]]

                if (ok(*new)):
                    new_id = pos2id(*new)
                    if (match[new_id] == -1 or edmon_match(match[new_id])):
                        match[now_id] = new_id
                        match[new_id] = now_id
                        return 1

            return 0

        def ok(y, x):
            if y >= 0 and y < n and x >= 0 and x < m and G[pos2id(y, x)]:
                return True
            return False

        ans = 0
        G = [1] * n * m

        for item in broken:
            G[pos2id(item[0], item[1])] = 0

        for id in range(n * m):
            now = id2pos(id)

            if (ok(*now) and match[id] == -1):
                vis = [0] * n * m
                ans += edmon_match(pos2id(now[0], now[1]))

        return ans

x = Solution()
n = int(input("输入棋盘大小n:"))
m = int(input("输入棋盘大小m:"))

broken = []
rows = eval(input("请输入有多少个坏了的格子数："))
columns = 2
 
for row in range(rows):
        broken.append([])#append精确插入一个元素，可以是元组也可以是序列。不可以超过一个或为空
        for column in range(columns):
            num = eval(input("请输入坐标："))
            broken[row].append(num)
v = int(x.domino(n,m,broken))
print(v)

结果如图：

对照题目：

与题目要求差不多，能接受，以后再改一改，先放在这。