博客

lintcode 553. 炸弹袭击

给定一个二维矩阵, 每一个格子可能是一堵墙 W,或者 一个敌人 E 或者空 0 (数字 ‘0’), 返回你可以用一个炸弹杀死的最大敌人数. 炸弹会杀死所有在同一行和同一列没有墙阻隔的敌人。 由于墙比较坚固，所以墙不会被摧毁.

code

def maxKilledEnemies(self, grid):
    # write your code here
    if grid is None or len(grid)==0 or len(grid[0])==0:
        return 0
    m = len(grid)
    n = len(grid[0])
    dp=[[0]*(n+2) for i in range (m+2)]
    res=[[0]*(n+2) for i in range (m+2)]
    result=0
    if grid[0][0]=='E':
        dp[0][0]=1
    for i in range(1,m+1,1):
        for j in range(1,n+1,1):
            if grid[i-1][j-1] == 'W':
                dp[i][j]=0
            elif grid[i-1][j-1] =='E':
                dp[i][j]=dp[i-1][j]+1
            else:
                dp[i][j]=dp[i-1][j]
                    
            res[i][j]=res[i][j]+dp[i][j]