# Java DP solultion, O(mn) time, O(mn) space, beats 90%

• Using only `O(mn)` memory for additional grid (not as perfect as (`O(m)` space solutions given by other users but anyway..) we can solve this problem through `O(4mn)` iterations. We just need to scan the grid from left to right and accumulate the sum of enemies by `dp[i][j]` from left since the last wall. Then we do the same from top to bottom, from right to left and finally from bottom to top. On each iteration we increase the `dp[i][j]` value by cumulative sum.

``````  public int maxKilledEnemies(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;

int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];

// from left to right
for (int i = 0; i < m; i++) {
int current = 0;
for (int j = 0; j < n; j++)
current = process(grid, dp, i, current, j);
}
// from top to bottom
for (int j = 0; j < n; j++) {
int current = 0;
for (int i = 0; i < m; i++)
current = process(grid, dp, i, current, j);
}
// from right to left
for (int i = 0; i < m; i++) {
int current = 0;
for (int j = n - 1; j >= 0; j--)
current = process(grid, dp, i, current, j);
}
int ans = 0;
// from bottom to top
for (int j = 0; j < n; j++) {
int current = 0;
for (int i = m - 1; i >= 0; i--) {
current = process(grid, dp, i, current, j);
if (grid[i][j] == '0')  ans = Math.max(ans, dp[i][j]);
}
}

return ans;
}

private int process(char[][] c, int[][] dp, int i, int current, int j) {
if (c[i][j] == 'W') current = 0;
if (c[i][j] == 'E') current++;
dp[i][j] += current;
return current;
}
``````

• This post is deleted!

• Good Solution!

``````public class Solution {
public int maxKilledEnemies(char[][] grid) {
if(grid==null||grid.length<1) return 0;

int[][] count=new int[grid.length][grid[0].length];

for(int i=0;i<grid.length;i++){
int current=0;
for(int j=0;j<grid[0].length;j++){
current=check(grid,count,i,j,current);
}
}

for(int i=0;i<grid.length;i++){
int current=0;
for(int j=grid[0].length-1;j>=0;j--){
current=check(grid,count,i,j,current);
}
}

for(int j=0;j<grid[0].length;j++){
int current=0;
for(int i=0;i<grid.length;i++){
current=check(grid,count,i,j,current);
}
}

int max=0;
for(int j=0;j<grid[0].length;j++){
int current=0;
for(int i=grid.length-1;i>=0;i--){
current=check(grid,count,i,j,current);
if(grid[i][j]=='0'){
max=Math.max(max,count[i][j]);
}
}
}
return max;
}

public int check(char[][] grid,int[][] count,int i,int j,int current){
if(grid[i][j]=='W'){
return 0;
}else if(grid[i][j]=='E'){
current++;
return current;
}else{//'0'
count[i][j]+=current;
return current;
}

}
}
``````

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