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.
Example:
For the given grid0 E 0 0E 0 W E0 E 0 0return 3. (Placing a bomb at (1,1) kills 3 enemies)
Credits:
Special thanks to 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 >& grid) { if (grid.empty() || grid[0].empty()) return 0; int m = grid.size(), n = grid[0].size(), res = 0; vector > v1(m, vector (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 >& 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; }};
参考资料：