Python, traverse horizontally and vertically.


  • 0
    B

    The idea is to traverse the grid horizontally and vertically and count enemy until a wall is seen. When a wall is seen backtrack to the last wall seen and replace all entries with enemy count in the copy of the grid. Finally, find max count among valid places in the copy the grid by using the original grid. Even though its O(n), n being the total elements in the grid, it is very long and very slow. Can be optimized by making it more pythonic.

        def maxKilledEnemies(self, grid):
            """
            :type grid: List[List[str]]
            :rtype: int
            """
            if len(grid) < 1 or len(grid[0]) < 1: return 0
            import copy
            grid1 = copy.deepcopy(grid)
            for i, val in enumerate(grid1):
                    left = 0
                    lastwall = -1
                    enemycnt = 0
                    while left <= len(grid[0])-1:
                            if val[left] == 'W' and lastwall ==-1:
                                    lastwall = left
                                    for j in range(left+1):
                                            val[j] = enemycnt
                                    left += 1
                                    enemycnt = 0
                                    continue
                            elif val[left] == 'W':
                                    for j in range(lastwall+1,left+1):
                                            val[j] = enemycnt
                                    lastwall = left
                                    left += 1
                                    enemycnt = 0
                                    continue
                            if val[left] == 'E': enemycnt +=1
                            left += 1
                    for j in range(lastwall+1,len(val)):
                            val[j] = enemycnt
            for i in range(len(grid[0])):
                    enemycnt = 0
                    for j in range(len(grid)):
                            if grid[j][i] == 'W':
                                    k = j-1
                                    while(k >= 0):
                                            if grid[k][i] == 'W': break
                                            grid1[k][i] += enemycnt
                                            k -= 1
                                    enemycnt = 0
                            if grid[j][i] == 'E':
                                    enemycnt +=1
                    k = j
                    while(k >= 0):
                            if grid[k][i] == 'W': break
                            grid1[k][i] += enemycnt
                            k -= 1
    
            maxbomb = 0
            for i, v in enumerate(grid1):
                    for j, c in enumerate(v):
                            if grid[i][j] == '0':   
                                    maxbomb = max(maxbomb, c)
            return maxbomb
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.