数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++中炸弹敌人
假设我们有一个二维网格，其中每个单元格要么是墙 '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] 的最大值
返回 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
256 次浏览
