Bomb Enemy


  • 0

    We have a 2D grid. Each cell is either a wall, an enemy or empty.

    For example (0-empty, X-enemy, Y-wall):

    0 X 0 0
    X 0 Y X
    0 X 0 0
    

    You have one bomb and you want to kill as many as possible enemies with it. The bomb will kill 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.

    Given such a grid, return the maximum enemies you can kill with one bomb.
    Note that you can only put the bomb at empty cell.

    In the example, if you put a bomb at (1,1) you will kill 3 enemies which is the best you can get. You can not kill the guy behind the wall at (1,3).


  • 0

    This seems to be an extension of leetcode problem, - "Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place."

    But with the constraint that there are walls.

    Also, this question is currently being asked at Google many times


  • 0
    G
    This post is deleted!

  • 1

    I think it can be solved using DP.

    Have two DP Arrays, one for Columns, and one for Rows.
    ie. dpRows[i,j] = number of X's that can be burst in the current row,
    and dpCols[i, j] = number of X's that can be burst in the current column.

    You need two n^2 iterations, one from Top left to bottom right, and one from bottom right to top left, updating both dpRows and dpColums.
    Whenever you encounter 'Y', a wall, dpRows[i, j] becomes 0;

    The result will be the maximum of dpRows[i,j] + dpCols[i,j] at the end.

    The below code should be done from TopLeft to BottomRight

    if(array[i][j] == 'X') {
        dpRows[i][j] = dpRows[i-1][j] + 1;
        dpCols[i][j] = dpCols[i][j-1] + 1;
    }else if(array[i][j] == '0'){
        dpRows[i][j] = dpRows[i-1][j];
        dpCols[i][j] = dpCols[i][j-1];
    }else {
        dpRows[i][j] = 0;
        dpCols[i][j] = 0;
    }
    

    Do the same from BottomRight to TopLeft

    if(array[i][j] == 'X') {
        dpRows[i][j] += dpRows[i+1][j] + 1;
        dpCols[i][j] += dpCols[i][j+1] + 1;
    }else if(array[i][j] == '0'){
        dpRows[i][j] += dpRows[i+1][j];
        dpCols[i][j] += dpCols[i][j+1];
    }else {
        dpRows[i][j] = 0;
        dpCols[i][j] = 0;
    }
    

    EDIT : i think it should be an update like this, when you're doing bottomright to top left
    dpRows[i][j] += because the previous values are updated. So I updated the above accordingly.

    Please let me know if you think this works.


  • 1

    @andyreadsall
    That is a very good idea, and I think there needs a change from BottomRight to TopLeft, and there is my code:

    public int bombEnemy(char[][] grid)
    {
    	int[][] row=new int[grid.length][grid[0].length+2],col=new int[grid.length+2][grid[0].length];
    	for(int i=0;i<grid.length;i++)
    	{
    		for(int j=0;j<grid[0].length;j++)
    		{
    			if(grid[i][j]=='0')
    			{
    				row[i][j+1]=row[i][j];
    				col[i+1][j]=col[i][j];
    			}
    			else if(grid[i][j]=='X')
    			{
    				row[i][j+1]=row[i][j]+1;
    				col[i+1][j]=col[i][j]+1;
    			}
    			else if(grid[i][j]=='Y')
    			{
    				row[i][j+1]=0;
    				col[i+1][j]=0;
    			}
    		}
    	}
    	for(int i=grid.length-1;i>=0;i--)
    	{
    		for(int j=grid[0].length-1;j>=0;j--)
    		{
    			if(grid[i][j]!='Y')
    			{
    				row[i][j+1]=Math.max(row[i][j+2],row[i][j+1]);
    				col[i+1][j]=Math.max(col[i+2][j], col[i+1][j]);
    			}
    		}
    	}
    	int max=0;
    	for(int i=0;i<grid.length;i++)
    		for(int j=0;j<grid[0].length;j++)
    			if(grid[i][j]=='0')
    				max=Math.max(max, row[i][j+1]+col[i+1][j]);
    	return max;
    }
    

  • 0

    @1337c0d3r
    Thank you for your suggestion.


  • 0
    R

    @jaqenhgar can you explain why would you go again from bottom right to top left?


  • 0
    A

    @jaqenhgar
    How would this work if during bottomright to top left, we are doing
    dpRows[i][j] += dpRows[i+1][j]; as in dpRows[n][n] might be 1 which means numbers of enemies that can be killed in nth row dpRows[n][n]=1 and suppose dpRows[n][n-1] is also 1 and arr[n][n] and arr[n][n-1] both are '0'. so value of dpRows[n][n-1] becomes 2 which is wrong.

    I have thought something like this .
    create 4 dparrays , 2 dpRows , 2 dpColums , one for topleft to bottom right and one for bottom right to top left . We add 2 dpRows ( while adding subtract 1 if arr[i][j]==X to remove overlapping) .
    We add 2 dpColums like above. Then we add two final dpRow and dpColumn and check the cells where arr[i][j]=='0'.

    Let me know your input.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.