text: # Time:  O(m * n)
  # Space: O(m * n)
  
  try:
      xrange          # Python 2
  except NameError:
      xrange = range  # Python 3
  
  
  class Solution(object):
      def maxKilledEnemies(self, grid):
          """
          :type grid: List[List[str]]
          :rtype: int
          """
          result = 0
          if not grid or not grid[0]:
              return result
  
          down = [[0 for _ in xrange(len(grid[0]))] for _ in xrange(len(grid))]
          right = [[0 for _ in xrange(len(grid[0]))] for _ in xrange(len(grid))]
          for i in reversed(xrange(len(grid))):
              for j in reversed(xrange(len(grid[0]))):
                  if grid[i][j] != 'W':
                      if i + 1 < len(grid):
                          down[i][j] = down[i + 1][j]
                      if j + 1 < len(grid[0]):
                          right[i][j] = right[i][j + 1]
                      if grid[i][j] == 'E':
                          down[i][j] += 1
                          right[i][j] += 1
  
          up = [0 for _ in xrange(len(grid[0]))]
          for i in xrange(len(grid)):
              left = 0
              for j in xrange(len(grid[0])):
                  if grid[i][j] == 'W':
                      up[j], left = 0, 0
                  elif grid[i][j] == 'E':
                      up[j] += 1
                      left += 1
                  else:
                      result = max(result,
                                   left + up[j] + right[i][j] + down[i][j])
  
          return result
  