package com.freetymekiyan.algorithms.level.medium;

/**
 * Given a 2D grid, each cell is either a wall 'W', an enemy 'E' or empty '0' (the number zero), return the maximum
 * enemies you can kill using one bomb.
 * The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since the
 * wall is too strong to be destroyed.
 * Note that you can only put the bomb at an empty cell.
 * <p>
 * Example:
 * For the given grid
 * <p>
 * | 0 E 0 0
 * | E 0 W E
 * | 0 E 0 0
 * <p>
 * return 3. (Placing a bomb at (1,1) kills 3 enemies)
 * <p>
 * Company Tags: Google
 * Tags: Dynamic Programming
 */
public class BombEnemy {

    public static final char WALL = 'W';
    public static final char ENEMY = 'E';
    public static final char EMPTY = '0';

    /**
     * DP.
     * Not exactly the same idea as general DP.
     * Just avoid duplicate searching for number of enemies each row and each column.
     * For each cell from left to right at each row:
     * | Use an integer rowHits to store the # of enemies can hit at this row.
     * | Only update rowHits when first column(j==0) or there is a wall at the left cell(grid[i][j-1] == 'W').
     * | Use an integer array colHits[] to store the # of enemies can hit at this column.
     * | Only update colHits when i == 0 or grid[i - 1][j] == 'W'.
     * | If grid[i][j] is empty:
     * |   Update result. result = max(result, rowHits + colHits[j]).
     * Return max.
     */
    public int maxKilledEnemies(char[][] grid) {
        if (grid == null) {
            return 0;
        }
        int m = grid.length;
        int n = m == 0 ? 0 : grid[0].length;
        int max = 0;
        int rowHits = 0;
        int[] colHits = new int[n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == WALL) { // Note that WALL cell can be skipped.
                    continue;
                }
                if (j == 0 || grid[i][j - 1] == WALL) {
                    rowHits = 0;
                    for (int k = j; k < n && grid[i][k] != WALL; k++) {
                        if (grid[i][k] == ENEMY) {
                            rowHits++;
                        }
                    }
                }
                if (i == 0 || grid[i - 1][j] == WALL) {
                    colHits[j] = 0;
                    for (int k = i; k < m && grid[k][j] != WALL; k++) {
                        if (grid[k][j] == ENEMY) {
                            colHits[j]++;
                        }
                    }
                }
                if (grid[i][j] == EMPTY) { // Only update when the cell is empty.
                    max = (rowHits + colHits[j]) > max ? rowHits + colHits[j] : max;
                }
            }
        }
        return max;
    }
}

@@ -49,16 +49,42 @@
 m;%0A%0A/**%0A
+ * 361. Bomb Enemy%0A * %3Cp%3E%0A
  * Given
@@ -684,29 +684,30 @@
 emy %7B%0A%0A    p
-ublic
+rivate
  static fina
@@ -722,37 +722,38 @@
 ALL = 'W';%0A    p
-ublic
+rivate
  static final ch
@@ -773,21 +773,22 @@
 ';%0A    p
-ublic
+rivate
  static 
@@ -842,376 +842,450 @@
   * 
-Not exactly the same idea as general DP.%0A     * Just avoid duplicate searching for number of enemies each row and each column.%0A     * For each cell from left to right at each row:%0A     * %7C Use an integer rowHits to store the # of enemies can hit at this row.%0A     * %7C Only update rowHits when first column(j==0) or there is a wall at the left cell(grid%5Bi%5D%5Bj-1%5D ==
+Avoid duplicate searching for number of enemies on the cell's left and top.%0A     * Since they will be already traversed.%0A     * So maintain an integer of number of enemy hits of current row, rowHits.%0A     * Maintain an array of integers of numbers of enemy hits of each column, colHits of size grid%5B0%5D.length.%0A     * Recurrence Relation:%0A     * rowHits = from this cell to the end of row or WALL. Re-calculate when j = 0 or left cell is a
  'W'
-)
 .%0A  
@@ -1293,119 +1293,78 @@
   * 
-%7C Use an integer array colHits%5B%5D to store the # of enemies can hit at this column.%0A     * %7C Only update colHits
+colHits = from this cell to the bottom of column or WALL. Re-calculate
  whe
@@ -1372,89 +1372,105 @@
  i =
-=
  0 or 
-grid%5Bi - 1%5D%5Bj%5D == 'W'.%0A     * %7C If grid%5Bi%5D%5Bj%5D is empty:%0A     * %7C
+top cell is a 'W'.%0A     * When the cell is 'E' (empty), we can place a bomb.%0A   
   
+*
  Update 
 resu
@@ -1469,36 +1469,20 @@
 ate 
-result. result = max(result,
+the max with
  row
@@ -1502,28 +1502,18 @@
 s%5Bj%5D
-).%0A     * Return max
+ if bigger
 .%0A  
@@ -1716,16 +1716,23 @@
  int max
+Enemies
  = 0;%0A  
@@ -1930,21 +1930,16 @@
 at WALL 
-cell 
 can be s
@@ -2743,42 +2743,30 @@
  max
- = (rowHits + colHits%5Bj%5D) %3E max ? 
+Enemies = Integer.max(
 rowH
@@ -2785,14 +2785,21 @@
 s%5Bj%5D
- :
+,
  max
+Enemies)
 ;%0A  
@@ -2856,16 +2856,23 @@
 turn max
+Enemies
 ;%0A    %7D%0A
@@ -2872,9 +2872,8 @@
 %0A    %7D%0A%7D
-%0A

update 361. Bomb Enemy with better explanation