// 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));
}
}
// 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