Python轰炸机游戏算法复杂度优化

Question

我正在尝试解决以下任务:

Each cell in a 2D grid contains either a wall ('W') or an enemy ('E'), or is empty ('0'). Bombs can destroy enemies, but walls are too strong to be destroyed. A bomb placed in an empty cell destroys all enemies in the same row and column, but the destruction stops once it hits a wall.

Return the maximum number of enemies you can destroy using one bomb.

Note that your solution should have O(field.length · field[0].length) complexity because this is what you will be asked during an interview.

Example

For

field = [["0", "0", "E", "0"],
         ["W", "0", "W", "E"],
         ["0", "E", "0", "W"],
         ["0", "W", "0", "E"]]

the output should be bomber(field) = 2.

Placing a bomb at (0, 1) or at (0, 3) destroys 2 enemies.

我实现了一个简单的解决方案，但它具有 O(n^2) 复杂度(n = 宽度*高度)。我怎样才能把它变成 O(n)？该任务被标记为“贪婪”，因此可能存在一种可行的贪婪方法。 这是天真的解决方案:

def bomber(field):

    if len(field) < 1:
        return 0

    h = len(field)
    w = len(field[0])
    max_enemies = 0

    for row in range(h):
        for col in range(w):

            if field[row][col] == "0":
                cur_max = 0
                cur_row = row
                cur_col = col

                while cur_row >= 0:
                    if field[cur_row][col] == "W":
                        break
                    if field[cur_row][col] == "E":
                        cur_max += 1
                    cur_row -= 1

                cur_row = row    

                while cur_row < h:
                    if field[cur_row][col] == "W":
                        break
                    if field[cur_row][col] == "E":
                        cur_max += 1
                    cur_row += 1

                cur_row = row

                while cur_col >= 0:
                    if field[row][cur_col] == "W":
                        break
                    if field[row][cur_col] == "E":
                        cur_max += 1
                    cur_col -= 1

                cur_col = col

                while cur_col < w:
                    if field[row][cur_col] == "W":
                        break
                    if field[row][cur_col] == "E":
                        cur_max += 1
                    cur_col += 1


                if cur_max > max_enemies:
                    max_enemies = cur_max

    return max_enemies 

Answer 1

如果你考虑单行，你可以确定在线性时间内在该行的每个方格中可见多少敌人(在同一行中)。

def ranges(c):
    i = 0
    while True:
        while i < len(c) and c[i] == "W":
            i += 1
        if i == len(c):
            return
        start = i
        enemies = 0
        while i < len(c) and c[i] != "W":
            if c[i] == "E":
                enemies += 1
            i += 1
        yield range(start, i), enemies

def enemies(c):
    answer = [0] * len(c)
    for r, enemies in ranges(c):
        for i in r:
            answer[i] = enemies
    return answer

这里的 ranges 函数返回“0”或“E”的连续范围，以及每个范围内的敌人数量。然后 enemies 使用这些范围构建一个向量，该向量显示每个方格可见的敌人数量。

例如:

>>> print enemies(["0", "E", "0", "E", "W", "0", "0", "W", "E"])
[2, 2, 2, 2, 0, 0, 0, 0, 1]

使用它，我们可以为每一行和每一列构造向量，然后在 O(W*H) 时间内找到最大值。代码使用了一个技巧:zip(*grid) 是 grid 的转置。

def best(grid):
    rows = [enemies(c) for c in grid]
    cols = [enemies(c) for c in zip(*grid)]
    return max(rows[i][j] + cols[j][i]
            for i in xrange(len(grid))
            for j in xrange(len(grid[0]))
            if grid[i][j] == '0')

并进行测试以确保其正常工作:

field = [["0", "0", "E", "0"],
         ["W", "0", "W", "E"],
         ["0", "E", "0", "W"],
         ["0", "W", "0", "E"]]

print best(field)