```
class Solution(object):
def maxKilledEnemies(self, grid):
if not grid: return 0
m,n = len(grid),len(grid[0])
def count(i,j,di,dj):
cnt = 0
while i < m and j < n and grid[i][j] != 'W':
cnt += 1 if grid[i][j]=='E' else 0
i += di
j += dj
return cnt
dp,ans = [0]*n,0
for i in xrange(m):
for j in xrange(n):
up,left = grid[i-1][j] if i > 0 else 'W',grid[i][j-1] if j > 0 else 'W'
cx = dp[j-1][0] if left != 'W' else count(i,j,0,1)
cy = dp[j][1] if up != 'W' else count(i,j,1,0)
dp[j] = (cx,cy)
if grid[i][j]=='0':
ans = max(ans,cx+cy)
return ans
```