# Bomb Enemies

## [Bomb Enemy](https://leetcode.com/problems/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).

```java
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 得存个数组才行。**

```java
    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;
    }
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mnunknown.gitbook.io/algorithm-notes/dong_tai_gui_hua/bomb_enemies.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.