# 4. 覆盖¶

## 1、题目描述¶

输入：n = 2, m = 3, broken = [[1, 0], [1, 1]]



输入：n = 3, m = 3, broken = []



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