27ms Java BFS solution - Beats 82.26%


  • 0
    T
    /*
    Essentially BFS:
        for each place where we can place a bomb (grid[i][j]=='0'), check horizontally and vertically and count the number of enemies present, and stop when we encounter 'W'.
    */
    
    class Solution {
        private int n;
        private int m;
        private int noEnemy = 0;
        private int maxEnemy = 0;
        public int maxKilledEnemies(char[][] grid) {
            n=grid.length;
            if(n==0) return 0;
            m=grid[0].length;
        
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    if(grid[i][j]!='0') continue;
                    bfsHorz(grid,i,j,0); //checks left
                    bfsHorz(grid,i,j,1); //checks right
                    bfsVert(grid,i,j,0); //checks up
                    bfsVert(grid,i,j,1); //checks down
                    if(noEnemy>maxEnemy) maxEnemy=noEnemy;
                    noEnemy=0;
                }
            }
            return maxEnemy;
        }
        
        public void bfsVert(char[][] grid, int i, int j, int lr){
            if(i<0||i>=n||j<0||j>=m||grid[i][j]=='W') return;
            
            if(grid[i][j]=='E') noEnemy++;
            
            if(lr==0) bfsVert(grid,i-1,j,lr);
            else if (lr==1) bfsVert(grid,i+1,j,lr);
            
            return;
        }
        
        public void bfsHorz(char[][] grid, int i, int j, int lr){
            if(i<0||i>=n||j<0||j>=m||grid[i][j]=='W') return;
            
            if(grid[i][j]=='E') noEnemy++;
            if(lr==0) bfsHorz(grid,i,j-1,lr);
            else if (lr==1) bfsHorz(grid,i,j+1,lr);
            
            return;
        }
        
    }
    

Log in to reply
 

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