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

• 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;
}
}``````

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