Accepted optimized brute-force


  • 0
    F

    Super easy to understand and code: we place a bomb on every empty position, only if the number of ennemies for this given row and column is higher than the maximum killed so far (otherwise even if we killed them all we wouldn't beat the current max). Complexity of O(something)

    /**
     * @param {character[][]} grid
     * @return {number}
     */
    var maxKilledEnemies = function(grid) {
        let max = 0;
        const h = grid.length;
        if (!h) { return 0 ;}
        const w = grid[0].length;
        if (!w) { return 0; }
        
        // Count how many ennemies are on each row and each column
        const {EByRows, EByCols} = countEnemiesByRowsAndCols(grid, h, w);
        
        /* For each empty position, blast a bomb if the number of ennemies
           on this row/col is higher than the current max */
        for (let row=0; row<h; row++) {
            for (let col=0; col<w; col++) {
                if (grid[row][col] !== '0') { continue; }
                if (EByRows[row] + EByCols[col] <= max) { continue; }
                max = Math.max(max, boom(grid, h, w, row, col));
            }
        }
        return max;
    };
    
    /* Blasts in 4 directions, one step at a time */
    function boom(grid, h, w, row, col) {
        return boomDir(grid, h, w, row-1, col, -1, 0) + 
               boomDir(grid, h, w, row+1, col, 1, 0) + 
               boomDir(grid, h, w, row, col-1, 0, -1) + 
               boomDir(grid, h, w, row, col+1, 0, 1);
    }
    
    function boomDir(grid, h, w, row, col, bottom, right) {
        if (row < 0 || col < 0 || row >= h || col >= w || grid[row][col] === 'W') { return 0; }
        const killed = grid[row][col] === 'E' ? 1 : 0;
        return killed + boomDir(grid, h, w, row+bottom, col+right, bottom, right);
    }
    
    function countEnemiesByRowsAndCols(grid, h, w) {
        let EByRows = [];
        for (let row=0; row<h; row++) {
            let e = 0;
            for (let col=0; col<w; col++) {
                if (grid[row][col] === 'E') { e++; }
            }
            EByRows[row] = e;
        }
        
        let EByCols = [];
        for (let col=0; col<w; col++) {
            let e = 0;
            for (let row=0; row<h; row++) {
                if (grid[row][col] === 'E') { e++; }
            }
            EByCols[col] = e;
        }
        return {EByRows, EByCols};
    }
    

Log in to reply
 

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