361. Bomb Enemy

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

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: You can only put the bomb at an empty cell.

Example:

Input: [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
Output: 3
Explanation: For the given grid,

0 E 0 0
E 0 W E
0 E 0 0

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

Code

class Solution {
    public int maxKilledEnemies(char[][] grid) {
        if(grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        int m = grid.length;
        int n = grid[0].length;
        int res = 0;
        
        int rowCount = 0;
        int[] colCount = new int[n];
        
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                // 扫描这一行
                // 1. 每一行刚开始的时候扫描
                // 2. 之前一个是墙,因此在之前的扫描被停止了,现在重新扫描
                // 0 E E W 0 E
                if(j == 0 || grid[i][j - 1] == 'W'){
                    rowCount = 0;
                    for(int k = j; k < n; k++){
                        if(grid[i][k] == 'W') break;
                        if(grid[i][k] == 'E') rowCount++;
                    }
                }

                // 扫描这一列
                // 在for循环第一行的时候i = 0,j = 0,1,2...时,colCount就完成了
                // 后面只有在遇到W的时候才会再执行
                if(i == 0 || grid[i - 1][j] == 'W'){
                    colCount[j] = 0;
                    for(int k = i; k < m; k++){
                        if(grid[k][j] == 'W') break;
                        if(grid[k][j] == 'E') colCount[j]++;
                    }
                }

                if(grid[i][j] == '0'){
                    res = Math.max(res, colCount[j] + rowCount);
                }
            }
        }

        return res;
    }
}