题目描述： 有一种大小为n x n的网格棋盘,棋盘中某些格子内有障碍物。 现在将棋盘的状况告诉你，请你求出最多可以在棋盘上放置多少棋子，保证放置的棋子 在同一行、同一列不会直接面对（中间无障碍物分隔，则为直接面对）。 棋盘的状态用一个字符串列表L告诉你，一个4x4的棋盘的例子如下： L=[“.X..”, “….”, “XX..”, “….”] 其中，X表示该位置有障碍物，.表示该位置无障碍物，棋子只能放在没有障碍物的地方。 现在给你n和L，请你输出最多可以再棋盘上放置的棋子个数。 如： n=4, L=[“.X..”, “….”, “XX..”, “….”] 则输出5
示例： 输入： n = 4 L = [“.X..”, “….”, “XX..”, “….”] 输出： 5
分析:
我们的目的是在棋盘里面放入更多的棋子，有一个比较直观的想法就是， 放入的这一个位置，影响到的位置越少越好。
因为我们每次放入一颗棋子都会让它 上下左右 的位置都无法再次放入棋子。如下图，当黄色位置放入棋子时，红色位置将都无法再次放入棋子。
以这个思路出发，每次找到 影响其他位置最少的位置，然后放入一颗棋子，直到最后整个棋盘没有一个位置可以放入棋子时结束。
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
nums = []
# 因为给出的数据里面每个列表元素是一个 字符串，所以我先转化为一个二维列表。
for i in range(n):
temp = []
for item in L[i]:
temp.append(1 if item == '.' else 0)
nums.append(temp)
# 计算四个方向会被影响的棋子数量，如果 flag 标记位 True, 那么就表示现在放入一颗棋子，并且将其他四个方向的位置标记为 不可放入。
def cal_value(x, y, flag):
temp = 0
# 右
for k in range(y+1, n):
if nums[x][k] == 0:
break
if flag:
nums[x][k] = 3
temp += nums[x][k]
# 下
for k in range(x+1, n):
if nums[k][y] == 0:
break
if flag:
nums[k][y] = 3
temp += nums[k][y]
# 上
for k in range(x-1, -1, -1):
if nums[k][y] == 0:
break
if flag:
nums[k][y] = 3
temp += nums[k][y]
# 左
for k in range(y-1, -1, -1):
if nums[x][k] == 0:
break
if flag:
nums[x][k] = 3
temp += nums[x][k]
return temp
ans = 0
# 一直重复操作
while True:
min_value = 99999
x, y = -1, -1
for i in range(n):
for j in range(n):
if nums[i][j] == 0 or nums[i][j] == 3:
continue
value = cal_value(i, j, 0)
if value < min_value:
min_value = value
x, y = i, j
# 表示没有一个位置可以放入棋子了，这个时候就应该退出。
if x == -1 and y == -1:
break
cal_value(x, y, 1)
nums[x][y] = 0
ans += 1
print(ans)