Bomb Enemy

Description

null

Solution(javascript)

// /** 1: Brute Force O(MN(M+N))
//  * @param {character[][]} grid
//  * @return {number}
//  */
// const maxKilledEnemies = function (grid) {
//   let max = 0
//   const getCount = (row, column) => {
//     let rowCount = 0
//     for (let i = 0; i < grid[row].length; i++) {
//       if (grid[row][i] === 'E') {
//         rowCount += 1
//       }
//       if (grid[row][i] === 'W') {
//         if (i < column) {
//           rowCount = 0
//         } else {
//           break
//         }
//       }
//     }
//     let columnCount = 0
//     for (let i = 0; i < grid.length; i++) {
//       if (grid[i][column] === 'E') {
//         columnCount += 1
//       }
//       if (grid[i][column] === 'W') {
//         if (i < row) {
//           columnCount = 0
//         } else {
//           break
//         }
//       }
//     }
//     return rowCount + columnCount
//   }
//   for (let row = 0; row < grid.length; row++) {
//     for (let column = 0; column < grid[row].length; column++) {
//       if (grid[row][column] === '0') {
//         const count = getCount(row, column)
//         max = Math.max(max, count)
//       }
//     }
//   }
//   return max
// }


/** 2: DP
 * @param {character[][]} grid
 * @return {number}
 */
const maxKilledEnemies = function (grid) {
  let max = 0
  const dp1 = grid.map(items => items.map(() => [0, 0]))
  const dp2 = grid.map(items => items.map(() => [0, 0]))
  const getCount = (row, column, dp = dp1) => {
    if (row < 0 || column < 0 || row >= grid.length || column >= grid[row].length) {
      return [0, 0]
    }
    return dp[row][column]
  }
  for (let row = 0; row < grid.length; row++) {
    for (let column = 0; column < grid[row].length; column++) {
      if (grid[row][column] === 'W') {
        dp1[row][column] = [0, 0]
      } else if (grid[row][column] === 'E') {
        dp1[row][column] = [getCount(row, column - 1)[0] + 1, getCount(row - 1, column)[1] + 1]
      } else {
        dp1[row][column] = [getCount(row, column - 1)[0], getCount(row - 1, column)[1]]
      }
    }
  }
  for (let row = grid.length - 1; row >= 0; row--) {
    for (let column = grid[row].length - 1; column >= 0; column--) {
      if (grid[row][column] === 'W') {
        dp2[row][column] = [0, 0]
      } else if (grid[row][column] === 'E') {
        dp2[row][column] = [getCount(row, column + 1, dp2)[0] + 1, getCount(row + 1, column, dp2)[1] + 1]
      } else {
        dp2[row][column] = [getCount(row, column + 1, dp2)[0], getCount(row + 1, column, dp2)[1]]
        max = Math.max(
          max,
          dp2[row][column][0] + dp2[row][column][1] + dp1[row][column][0] + dp1[row][column][1],
        )
      }
    }
  }

  return max
}