[LeetCode] 361. Bomb Enemy

[grandyang]

 

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)

Credits:
Special thanks to @memoryless for adding this problem and creating all test cases.

 

这道题相当于一个简单的炸弹人游戏，让博主想起了小时候玩的红白机的炸弹人游戏（小霸王学习机，其乐无穷！！），放一个炸弹，然后爆炸后会炸出个‘十’字，上下左右的东西都炸掉了。这道题是个简化版，字母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(), res = 0;
        vector<vector<int>> v1(m, vector<int>(n, 0)), v2 = v1, v3 = v1, v4 = v1;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int t = (j == 0 || grid[i][j] == 'W') ? 0 : v1[i][j - 1];
                v1[i][j] = grid[i][j] == 'E' ? t + 1 : t;
            }
            for (int j = n - 1; j >= 0; --j) {
                int t = (j == n - 1 || grid[i][j] == 'W') ? 0 : v2[i][j + 1];
                v2[i][j] = grid[i][j] == 'E' ? t + 1 : t;
            }
        }
        for (int j = 0; j < n; ++j) {
            for (int i = 0; i < m; ++i) {
                int t = (i == 0 || grid[i][j] == 'W') ? 0 : v3[i - 1][j];
                v3[i][j] = grid[i][j] == 'E' ? t + 1 : t;
            }
            for (int i = m - 1; i >= 0; --i) {
                int t = (i == m - 1 || grid[i][j] == 'W') ? 0 : v4[i + 1][j];
                v4[i][j] = grid[i][j] == 'E' ? t + 1 : t;
            }
        }
        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;
    }
};

 

在论坛里看到了史蒂芬大神提出的另一种解法，感觉挺巧妙，就搬了过来。这种解法比较省空间，写法也比较简洁，需要一个 rowCnt 变量，用来记录到下一个墙之前的敌人个数。还需要一个数组 colCnt，其中 colCnt[j] 表示第j列到下一个墙之前的敌人个数。算法思路是遍历整个数组 grid，对于一个位置 grid[i][j]，对于水平方向，如果当前位置是开头一个或者前面一个是墙壁，开始从当前位置往后遍历，遍历到末尾或者墙的位置停止，计算敌人个数。对于竖直方向也是同样，如果当前位置是开头一个或者上面一个是墙壁，开始从当前位置向下遍历，遍历到末尾或者墙的位置停止，计算敌人个数。可能会有人有疑问，为啥 rowCnt 就可以用一个变量，而 colCnt 就需要用一个数组呢，为啥 colCnt 不能也用一个变量呢？原因是由遍历顺序决定的，这里是逐行遍历的，在每行的开头就统计了该行的敌人总数，所以再该行遍历没必要用数组，但是每次移动时就会换到不同的列，总不能没换个列就重新统计一遍吧，所以就在第一行时一起统计了存到数组中供后来使用。有了水平方向和竖直方向敌人的个数，那么如果当前位置是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, rowCnt, 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;
    }
};

 

Github 同步地址：

#361

 

参考资料：

https://leetcode.com/problems/bomb-enemy/

https://leetcode.com/problems/bomb-enemy/discuss/83387/short-omn-time-on-space-solution

 

LeetCode All in One 题目讲解汇总(持续更新中...)