题目描述: 有一种大小为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)