LeetCode 361 [Bomb Enemy]

作者: Jason_Yuan | 来源:发表于2016-09-12 09:24 被阅读640次

    原题

    Given a 2D grid, each cell is either a wall 'W', an enemy 'E' or empty '0' (the number zero), return the maximum enemies you can kill using one bomb.The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since the wall is too strong to be destroyed.

    样例
    给出如下矩阵

    0 E 0 0
    E 0 W E
    0 E 0 0
    

    返回3,把炸弹放在(1, 1)可以炸死3个敌人

    解题思路

    • 双重for循环遍历矩阵
    • 如果是第一行或者第一列,就记录一下current到下一个墙中间的敌人数量,知道下一次遇见墙,重新计算这面墙之后到下一面墙中间的敌人数量

    完整代码

    class Solution:
        # @param {character[][]} grid Given a 2D grid, each cell is either 'W', 'E' or '0'
        # @return {int} an integer, the maximum enemies you can kill using one bomb
        def maxKilledEnemies(self, grid):
            # Write your code here
            m, n = len(grid), 0
            if m:
                n = len(grid[0])
            
            res, rows = 0, 0
            cols = [0 for i in range(n)]
            
            for i in range(m):
                for j in range(n):
                    if j == 0 or grid[i][j - 1] == "W":
                        rows = 0
                        for k in range(j, n):
                            if grid[i][k] == "W":
                                break
                            if grid[i][k] == "E":
                                rows += 1
                            
                    if i == 0 or grid[i - 1][j] == "W":
                        cols[j] = 0
                        for k in range(i, m):
                            if grid[k][j] == "W":
                                break
                            if grid[k][j] == "E":
                                cols[j] += 1
                    
                    if grid[i][j] == "0" and rows + cols[j] > res:
                        res = rows + cols[j]
            
            return res
    

    相关文章

      网友评论

        本文标题:LeetCode 361 [Bomb Enemy]

        本文链接:https://www.haomeiwen.com/subject/sqieettx.html