掃雷Python編碼挑戰

規則非常簡單：我們將地雷所在位置的網格作為輸入，然后輸出一個網格，其中每個單元格都明確表示周圍的地雷數量。

這意味著我們需要檢查每個單元格的 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 分鐘的時間來解決這個問題，但我一生都無法弄清楚有人會如何解決這個問題。

uj5u.com熱心網友回復：

如果你想最小化空間使用，對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)
        ))

不過，對于 仍然是 O(n) 時間array；在這方面真的不可能改進。任何解決方案都必須查看板上的每個單元格，這意味著它永遠不可能比 O(n) 快。

uj5u.com熱心網友回復：

到達相鄰位置的一種簡單方法是根據行號和列號為 8 個相鄰單元格準備一個偏移量串列。您可以使用“O”單元格上的零和地雷位置上的“X”來初始化結果矩陣。然后，當相鄰位置在板的范圍內并包含“X”時，每個位置上的嵌套回圈可以通過偏移量將 1 添加到“零”單元格：

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 倍

標籤：Python 蟒蛇-3.x 算法 扫雷艇

上一篇：如何從給定的陣列和函式為給定的演算法撰寫matlab代碼？

下一篇：獲取字串中插入字符的所有組合