C++ 中的炸弹
假设我们有一个 2D 网格，其中每个单元格要么是墙"W"，要么是敌人"E"，要么是空的"0"，我们必须找到使用一个炸弹可以杀死的最大敌人数。炸弹会杀死从放置点到击中墙壁为止同一行和列中的所有敌人。而且我们只能在空白处放置炸弹。
因此，如果输入如下
那么输出将是 3，因为将炸弹放在绿色位置，它将杀死三个敌人。
为了解决这个问题，我们将遵循以下步骤 −
ret := 0
n := 网格的行数，m := 网格的列数
定义一个大小为 m 的数组 colCnt
用于初始化 i := 0，当 i < n，更新(将 i 增加 1)，执行 −
初始化 j := 0，当 j < m，更新(将 j 增加 1)，执行 −
如果 j 为零或 grid[i, j] 与 'W' 相同，则 −
rowCnt := 0
如果 grid[i, j] 与 'W' 相同，则 −
k := j + 1
否则
k := j
对于 k < m 且 grid[i, k] 不等于 'W'，则更新(将 k 增加 1)，执行 −
当 (grid[i, k] 为 'E') 时，rowCnt := rowCnt + 1，否则为 0
如果 i 为零或 grid[i, j] 与 'W' 相同，则 −
colCnt[j] := 0
如果 grid[i, j] 与 'W' 相同，则 −
k := i + 1
否则
k := i
如果 k < n 且 grid[k, j] 不等于 'W'，则更新(将 k 增加 1)，执行 −
当 (grid[k, j] 为 'E') 时，colCnt[j] := colCnt[j] + 1，否则为 0
如果 grid[i, j] 与 '0' 相同，则 −
ret := ret 和 rowCnt + colCnt[j] 的最大值
return ret
示例
让我们看看下面的实现以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxKilledEnemies(vector<vector<char>>& grid) {
int ret = 0;
int n = grid.size();
int m = n ? grid[0].size() : 0;
int rowCnt = 0;
vector<int< colCnt(m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!j || grid[i][j] == 'W') {
rowCnt = 0;
int k;
if (grid[i][j] == 'W')
k = j + 1;
else
k = j;
for (; k < m && grid[i][k] != 'W'; k++) {
rowCnt += (grid[i][k] == 'E');
}
}
if (!i || grid[i][j] == 'W') {
colCnt[j] = 0;
int k;
if (grid[i][j] == 'W')
k = i + 1;
else
k = i;
for (; k < n && grid[k][j] != 'W'; k++) {
colCnt[j] += (grid[k][j] == 'E');
}
}
if (grid[i][j] == '0') {
ret = max(ret, rowCnt + colCnt[j]);
}
}
}
return ret;
}
};
main(){
Solution ob;
vector<vector<char>> v = {{'0','E','0','0'},{'E','0','W','E'},{'0','E','0','0'}};
cout << (ob.maxKilledEnemies(v));
}
输入
{{'0','E','0','0'},{'E','0','W','E'},{'0','E','0','0'}}
输出
3
