Java 44ms simple O(mn) solution, use one m*n array to do dp.


  • 0

    The key point of this problem is that dp need be called in 4 directions(up to down, down to up, left to right, right to left). So the time complexity is O(4mn). I use one extra array to save some space.

    public class Solution {
    public int ecount;
    public int last0;
    public int[][] bombcount;
    private void conds(char[][] grid, int[][] bombcount, int i, int j,int ecount, int last0){
                if(grid[i][j]=='E'){
                    this.ecount++;
                }
                else if(grid[i][j]=='W'){
                    this.last0 = 0;
                    this.ecount = 0;
                }
                else{//grid[i][j] = 0 
                    this.bombcount[i][j] += last0+ecount;
                    this.last0 += ecount;
                    this.ecount = 0;
                }
    }
    public int maxKilledEnemies(char[][] grid) {
        int m = grid.length;
        if(m==0) return 0;
        int n = grid[0].length;
        if(n==0) return 0;
        bombcount = new int[m][n];
        for(int i = 0;i<m;i++){
            ecount = 0;
            last0 = 0;
            for(int j = 0;j<n;j++){//left to right
                conds(grid,bombcount, i, j, ecount, last0);
            }
            ecount = 0;
            last0 = 0;
            for(int j = n-1;j>=0;j--){
                conds(grid,bombcount, i, j, ecount, last0);
            }
        }
        for(int j = 0;j<n;j++){
            ecount = 0;
            last0 = 0;
            for(int i = 0;i<m;i++){//top to down
                conds(grid,bombcount, i, j, ecount, last0);
            }
            ecount = 0;
            last0 = 0;
            for(int i = m-1;i>=0;i--){
                conds(grid,bombcount, i, j, ecount, last0);
            }
        }
        int max = 0;
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                max = bombcount[i][j]>max?bombcount[i][j]:max;
            }
        }
        return max;
    }
    }

Log in to reply
 

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