361. Bomb Enemy (Medium)

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

Example:

For the given grid

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

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

Solution 1: Brute Force 239ms

这道题相当于一个简单的炸弹人游戏，让我想起了小时候玩的红白机的炸弹人游戏，放一个炸弹，然后爆炸后会炸出个‘十’字，上下左右的东西都炸掉了。这道题是个简化版，字母E代表敌人，W代表墙壁，这里说明了炸弹无法炸穿墙壁。数字0表示可以放炸弹的位置，让我们找出一个放炸弹的位置可以炸死最多的敌人。那么我最开始想出的方法是建立四个累加数组v1, v2, v3, v4，其中v1是水平方向从左到右的累加数组，v2是水平方向从右到左的累加数组，v3是竖直方向从上到下的累加数组，v4是竖直方向从下到上的累加数组，我们建立好这个累加数组后，对于任意位置(i, j)，其可以炸死的最多敌人数就是v1[i][j] + v2[i][j] + v3[i][j] + v4[i][j]，最后我们通过比较每个位置的累加和，就可以得到结果，参见代码如下：

class Solution {
public:
    int maxKilledEnemies(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> v1(m, vector<int>(n)), v2 = v1, v3 = v1, v4 = v1;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (j == 0 || grid[i][j] == 'W') v1[i][j] = 0;
                else v1[i][j] = v1[i][j-1];
                if (grid[i][j] == 'E') v1[i][j] += 1;
            }
            for (int j = n-1; j >= 0; --j) {
                if (j == n-1 || grid[i][j] == 'W') v2[i][j] = 0;
                else v2[i][j] = v2[i][j+1];
                if (grid[i][j] == 'E') v2[i][j] += 1;
            }
        }

        for (int j = 0; j < n; ++j) {
            for (int i = 0; i < m; ++i) {
                if (i == 0 || grid[i][j] == 'W') v3[i][j] = 0;
                else v3[i][j] = v3[i-1][j];
                if (grid[i][j] == 'E') v3[i][j] += 1;
            }
            for (int i = m-1; i >= 0; --i) {
                if (i == m-1 || grid[i][j] == 'W') v4[i][j] = 0;
                else v4[i][j] = v4[i+1][j];
                if (grid[i][j] == 'E') v4[i][j] += 1;
            }
        }
        int res = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '0') {
                    res = max(res, v1[i][j]+v2[i][j]+v3[i][j]+v4[i][j]);
                }
            }
        }
        return res;
    }
};

Solution 2: DP 89ms

我在论坛里看到了史蒂芬大神提出的另一种解法，感觉挺巧妙，就搬了过来。这种解法比较省空间，写法也比较简洁，需要一个rowCnt变量，用来记录到下一个墙之前的敌人个数。还需要一个数组colCnt，其中colCnt[j]表示第j列到下一个墙之前的敌人个数。算法思路是遍历整个数组grid，对于一个位置grid[i][j]，对于水平方向，如果当前位置是开头一个或者前面一个是墙壁，我们开始从当前位置往后遍历，遍历到末尾或者墙的位置停止，计算敌人个数。对于竖直方向也是同样，如果当前位置是开头一个或者上面一个是墙壁，我们开始从当前位置向下遍历，遍历到末尾或者墙的位置停止，计算敌人个数。有了水平方向和竖直方向敌人的个数，那么如果当前位置是0，表示可以放炸弹，我们更新结果res即可，参见代码如下：

class Solution {
public:
    int maxKilledEnemies(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        int m = grid.size(), n = grid[0].size(), res = 0;
        int rowCnt = 0, colCnt[n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (j == 0 || grid[i][j-1] == 'W') {
                    rowCnt = 0;
                    for (int k = j; k < n && grid[i][k] != 'W'; ++k) {
                        rowCnt += grid[i][k] == 'E';
                    }
                }

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

                if (grid[i][j] == '0') {
                    res = max(res, rowCnt+colCnt[j]);
                }

            }
        }

        return res;
    }
};