跳转至

4. 覆盖

1、题目描述

你有一块棋盘,棋盘上有一些格子已经坏掉了。你还有无穷块大小为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]]。(见下图)

img

示例 2:

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

img

限制:

  1. 1 <= n <= 8
  2. 1 <= m <= 8
  3. 0 <= b <= n * m

2、解题思路

  • 贪心法
  • 首先设置一个访问数组,与原数组相同,损坏位置使用1标识,并且四周围绕一圈1
  • 从开始位置判断,如果某一个位置四周都是1,那么肯定无法放下一个骨牌,直接设置为访问过
  • 如果位置周围有3个1,这时候表示只有一条路径可走,将这两个点标识为已走过
  • 如果找不到周围有4个1或者3个1的位置,找周围有2个1的位置选其中一条路径
  • 直到没有未走过的路径为止
class Solution:
    def domino(self, n: int, m: int, broken: List[List[int]]) -> int:
        visited = [[0 for _ in range(m + 2)] for _ in range(n + 2)]
        visited[0] = [1] * (m + 2)
        visited[-1] = [1] * (m + 2)

        for i in range(n):
            visited[i + 1][0] = 1
            visited[i + 1][-1] = 1

        for bx, by in broken:
            visited[bx + 1][by + 1] = 1

        # 上下左右-坐标
        surround = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        #
        def get_surrounds(x, y):
            ones = 0
            for dx, dy in surround:
                x1, y1 = x + dx, y + dy
                if visited[x1][y1]:
                    ones += 1
            return ones

        def set_visited(x, y):
            visited[x][y] = 1
            for dx, dy in surround:
                x1, y1 = x + dx, y + dy
                if not visited[x1][y1]:
                    visited[x1][y1] = 1
                    break

        flag = True
        ans = 0

        while flag:
            flag = False
            for i in range(1, n + 1):
                for j in range(1, m + 1):
                    if not visited[i][j]:

                        ones_count = get_surrounds(i, j)
                        if ones_count == 4:
                            visited[i][j] = 1
                            flag = True
                        elif ones_count == 3:
                            flag = True
                            ans += 1
                            set_visited(i, j)
            if not flag:
                for i in range(1, n + 1):
                    for j in range(1, m + 1):
                        if not flag and not visited[i][j]:
                            ones_count = get_surrounds(i, j)
                            if ones_count == 2:
                                ans += 1
                                set_visited(i, j)
                                flag = True
        return ans