扫雷Python编码挑战

Question

规则非常简单：我们将地雷所在的网格作为输入，并输出一个网格，其中每个单元格都明确地表示其周围的地雷数量

这意味着我们需要检查每个单元格的8个位置：左上、中上、右上、右中、左中、左下、中下和右下。如果这些细胞中有任何一个含有地雷，我们正在检查的细胞就会变成我们刚刚统计的地雷数量。

示例输入：

input = ["OOOXXXOXX", "XXXXXXOXX", "XOOXXXXXX", "OOXXOXOXX", "XXXXXXXXX"]

我们为此输出：

2 3 4 X X X 4 X X
X X X X X X 7 X X
X 5 6 X X X X X X
3 5 X X 8 X 8 X X
X X X X X X X X X

现在是我的工作解决方案：

def minesweeper(array):
# Vertical iterations
for lineIndex in range(len(array)):

line = array[lineIndex]
outputLine = []
# Horizontal iterations
for cellIndex in range(len(line)):

# Check cell content
if (line[cellIndex] == "O"):
northIndex = lineIndex - 1
eastIndex = cellIndex - 1
southIndex = lineIndex + 1
westIndex = cellIndex + 1
verticals = [northIndex, lineIndex, southIndex]
horizontals = [eastIndex, cellIndex, westIndex]
counter = 0
for v in verticals:
for h in horizontals:
if v >= 0 and h >= 0:
if array[v][h] == 'X':
counter += 1
outputLine.append(str(counter))
else:
outputLine.append("X")
print(' '.join(outputLine))

我相信，就时空复杂性而言，总的来说，一定有更好的解决方案。在一次编码挑战中，我有15分钟的时间来解决这个问题，但我一辈子都不知道别人会如何处理这个问题。

Answer 1

如果您想最大限度地减少空间使用，请使用生成器为每行输出join，而不是分配列表。您还可以通过使用enumerate而不是使用for index in range(...)来迭代列表，并最大限度地减少您分配的额外变量的数量，从而获得一些恒定因素时间优势。

def minesweeper(array):
for y, line in enumerate(array):
print(' '.join(
"X" if cell == "X" else str(sum(
cell == "X"
for line in array[max(0, y-1):min(len(array), y+2)]
for cell in line[max(0, x-1):min(len(line), x+2)]
)) for x, cell in enumerate(line)
))

然而，相对于array，它仍然是O(n(时间；在这方面真的不可能改进。任何解决方案都必须查看板中的每个单元，这意味着它永远不可能比O(n(快。

Answer 2

到达相邻位置的一个简单方法是根据行号和列号为8个相邻单元格准备一个偏移列表。您可以在"0"上初始化结果矩阵；O〃；细胞和"；X〃；在地雷阵地上。然后，当相邻位置在板的范围内并且包含"0"时，每个位置上的嵌套循环可以经过偏移以将1加到"0"单元；X〃：

board = ["OOOXXXOXX",
"XXXXXXOXX",
"XOOXXXXXX",
"OOXXOXOXX",
"XXXXXXXXX"]
offsets = [ (-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1) ]
result  = [ [[0,"X"][c=="X"] for c in row] for row in board] # initialize
for r,s in enumerate(board):  # go through board rows
for c,m in enumerate(s):  # co through row's columns
for dr,dc in [] if m=="X" else offsets: # neighbours of "O" cells
if r+dr in range(len(board)) and c+dc in range(len(s)):
result[r][c] += board[r+dr][c+dc] == "X" # count bombs

输出：

for row in result:
for c in row:
print(c,end=" ")
print()
2 3 4 X X X 4 X X 
X X X X X X 7 X X 
X 5 6 X X X X X X 
3 5 X X 8 X 8 X X 
X X X X X X X X X

如果你想避免混淆索引和偏移量，你可以准备8个移位的板副本(每个方向一个(，并使用zip((将它们组合成每个位置的邻居元组。然后计算合并元组中X的数量：

emptyRow   = ["."*len(board[0])]
left       = [ "."+row for row in board ]
right      = [ row[1:]+"." for row in board ]
up         = emptyRow + board
down       = board[1:] + emptyRow
upLeft     = emptyRow + left
upRight    = emptyRow + right
downLeft   = left[1:] + emptyRow
downRight  = right[1:] + emptyRow
neighbours = (board,left,right,up,down,upLeft,upRight,downLeft,downRight)
result     = [ [n.count("X") if m=="O" else m for m,*n in zip(*rows)]
for rows in zip(*neighbours) ]
for row in result:
for c in row:
print(c,end=" ")
print()
2 3 4 X X X 4 X X 
X X X X X X 7 X X 
X 5 6 X X X X X X 
3 5 X X 8 X 8 X X 
X X X X X X X X X 

这比基于索引/偏移量的解决方案快大约5倍