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使用这些范围构造一个向量，该向量显示每平方米有多少敌人可见。在

例如：

^{pr2}$

利用这个方法，我们可以为每一行和每列构造向量，然后求出O（W*H）时间内的最大值。{cd3>{cd3}是转置码。在

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)