Bomb Enemies

Bomb Enemy

非常明显的记忆化搜索，核心问题只有一个：

• 给定一行/列，如何最高效地计算出每个位置在当前 行/列 上能炸到的最大值。

跑了个简单 Case，结论是，雷可以穿人。和炸弹人差不多。。。

于是下图这个简单暴力的方法就出来了，因为写的比较匆忙没有进行任何简洁性的优化，所以看着就不能忍，需要改进。

思路如下：

• 建立 rowMax[][] 和 colMax[][] 矩阵，记录对于每一个位置 (i, j) ，其在 row / col 上能炸到的最大敌人数

• 遍历每一个 row / col

• 先建一个数组，从左向右扫，保存一个 maxCount 变量，遇到 'W' 就归零，遇到 'E' 就增加，遇到 '0' 不变，一路上把每个位置赋值成 maxCount;

• 然后再从右往左，在每个位置上取新的 maxCount (因为对于每个区间，这次一定会先看到最大的 count 数)，遇到 '0' 就赋值，遇到 'E' 只取 maxCount，赋值0 (不能在敌人头上扔炸弹)，遇到 'W' maxCount 归零，赋值也是0.

因此对于每一行，复杂度都是 O(cols)，对于每一列，复杂度都是 O(rows)，整个预处理的过程用时为 O(rows * cols)，最后的扫描也是 P(rows * cols).

public class Solution {
    public int maxKilledEnemies(char[][] grid) {
        if(grid == null || grid.length == 0) return 0;

        int rows = grid.length;
        int cols = grid[0].length;

        int[][] rowMax = new int[rows][cols];
        int[][] colMax = new int[rows][cols];

        for(int i = 0; i < rows; i++){
            int[] count = new int[cols];
            int enemyCount = 0;
            for(int j = 0; j < cols; j++){
                if(grid[i][j] == 'W') enemyCount = 0;
                if(grid[i][j] == 'E') enemyCount ++;

                count[j] = enemyCount;
            } 
            int maxCount = 0;
            for(int j = cols - 1; j >= 0; j--){
                if(grid[i][j] == '0') {
                    maxCount = Math.max(maxCount, count[j]);
                    rowMax[i][j] = maxCount;
                }
                if(grid[i][j] == 'W') {
                    maxCount = 0;
                    rowMax[i][j] = 0; 
                }
                if(grid[i][j] == 'E') {
                    maxCount = Math.max(maxCount, count[j]);
                    rowMax[i][j] = 0; 
                }
            }
        }

        for(int i = 0; i < cols; i++){
            int[] count = new int[rows];
            int enemyCount = 0;
            for(int j = 0; j < rows; j++){
                if(grid[j][i] == 'W') enemyCount = 0;
                if(grid[j][i] == 'E') enemyCount ++;

                count[j] = enemyCount;
            } 
            int maxCount = 0;
            for(int j = rows - 1; j >= 0; j--){
                if(grid[j][i] == '0') {
                    maxCount = Math.max(maxCount, count[j]);
                    colMax[j][i] = maxCount;
                }
                if(grid[j][i] == 'W') {
                    maxCount = 0;
                    colMax[j][i] = 0; 
                }
                if(grid[j][i] == 'E') {
                    maxCount = Math.max(maxCount, count[j]);
                    colMax[j][i] = 0; 
                }
            }
        }

        int max = 0;
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                max = Math.max(max, rowMax[i][j] + colMax[i][j]);
            }
        }

        return max;
    }
}

上面我第一次 AC 的代码能过，但是代码量略大，而且空间使用也不算经济。下面是参考 LC 论坛上的解法：

• 核心思想是，row 和 col 的缓存只会在(上/左)就是 "W" 时需要更新

• 因此初始化或者(上/左)是墙的时候，可以计算一个临时结果，在遇到另一个 "W" 时停止；

• 这个缓存在遇到新一个(上/左)是 "W" 的格子之前，都是有效的，无需重复计算。

• 考虑到循环是 row , col 的顺序，我们的 rowCache 一个变量就够了，但是 colCache 得存个数组才行。

    public int maxKilledEnemies(char[][] grid) {
        if(grid == null || grid.length == 0) return 0;
        int rows = grid.length;
        int cols = grid[0].length;

        int max = 0;
        int rowCache = 0;
        int[] colCache = new int[cols];

        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                if(j == 0 || grid[i][j - 1] == 'W'){
                    rowCache = 0;
                    for(int k = j; k < cols && grid[i][k] != 'W'; k++){
                        rowCache += grid[i][k] == 'E' ? 1 : 0;
                    }
                }

                if(i == 0 || grid[i - 1][j] == 'W'){
                    colCache[j] = 0;
                    for(int k = i; k < rows && grid[k][j] != 'W'; k++){
                        colCache[j] += grid[k][j] == 'E' ? 1 : 0;
                    }
                }

                if(grid[i][j] == '0') max = Math.max(max, rowCache + colCache[j]);
            }
        }

        return max;
    }