Bomb Enemy

//  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.

// Example:
// For the given grid

// 0 E 0 0
// E 0 W E
// 0 E 0 0

// return 3. (Placing a bomb at (1,1) kills 3 enemies)

/**
Solution:

*/
 public class BombEnemy {
     public static int maxKilledEnemies(char[][] grid) {
        if(grid == null || grid.length == 0 ||  grid[0].length == 0) {
            return 0;
        }

        int max = 0;
        int row = 0;
        int[] col = new int[grid[0].length];//why array unlike a single value for the row?
//col arrays because the row entries only impact one row but col entries impact multiple rows


        for(int i = 0; i<grid.length; i++) {
            for(int j = 0; j<grid[0].length;j++) {
                if(grid[i][j] == 'W') {
                    continue;
                }
//find the count of 'E' between two walls in a row
//if this first col of the row or if the previous col in this row was a wall, we need to find the number of cells with 'E' in the row
//if no wall is encountered in the previous col, the previusly computed value is used instead
                if(j == 0 || grid[i][j-1] == 'W') {
                     row = killedEnemiesRow(grid, i, j);
                }
//if this is the first row or the previous row was a wall, we need to find the number of cells with 'E' in the col
//if no wall is encountered in the previous row, the previously computed value is used instead
                if(i == 0 || grid[i-1][j] == 'W') {
                     col[j] = killedEnemiesCol(grid,i,j);
                }
// if this is a position to place the bomb, get the current max
                if(grid[i][j] == '0') {
System.out.println("row "+i+" col:"+j+" row and col[j] "+row+","+col[j]+" max:"+max);
                    max = (row + col[j] > max) ? row + col[j] : max;
                }
            }
        }
       
        return max;
    }

    //calculate killed enemies for row i from column j
    private static int killedEnemiesRow(char[][] grid, int i, int j) {
        int num = 0;
        while(j <= grid[0].length-1 && grid[i][j] != 'W') {
            if(grid[i][j] == 'E') {
                num++;
            }
            j++;
        }
        return num;
    }

    //calculate killed enemies for  column j from row i
    private static int killedEnemiesCol(char[][] grid, int i, int j) {
        int num = 0;
        while(i <= grid.length -1 && grid[i][j] != 'W'){
            if(grid[i][j] == 'E') {
                num++;
            }
            i++;
        }
        return num;
    }

public static void main(String[] args){
char[][] mat = new char[3][4];
mat[0] = new char[]{'0', 'E', '0', '0'};
mat[1] = new char[]{'E', '0', 'W', 'E'};
mat[2] = new char[]{'E', 'E', 'E', '0'};
System.out.println(maxKilledEnemies(mat));

}
}

No comments:

Post a Comment