数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++程序：如何找到放置炸弹以杀死最多敌人的位置？
假设我们有一个包含三种不同值的二维矩阵：2、1 和 0，其中 2 表示敌人，1 表示墙壁，0 表示空单元格。我们必须找到使用一枚炸弹可以杀死的最大敌人数量。炸弹会杀死从放置点开始同一行和同一列的所有敌人，直到遇到墙壁。并且我们只能在空白单元格上放置炸弹。
因此，如果输入类似于
则输出将为 3，因为我们可以在绿色方块处放置炸弹以杀死最多 3 个敌人。
ret := 0
n := 网格的行数，m := 网格的列数
定义一个大小为 m 的数组 colCnt
初始化 i := 0，当 i < n 时，更新（i 增加 1），执行以下操作：
初始化 j := 0，当 j < m 时，更新（j 增加 1），执行以下操作：
如果 j 为零或 grid[i, j] 等于 1，则：
rowCnt := 0
如果 grid[i, j] 等于 1，则：
k := j + 1
否则
k := j
对于 k < m 且 grid[i, k] 不等于 1，更新（k 增加 1），执行以下操作：
当 (grid[i, k] 为 2) 时，rowCnt := rowCnt + 1，否则为 0
如果 i 为零或 grid[i, j] 等于 1，则：
colCnt[j] := 0
如果 grid[i, j] 等于 1，则：
k := i + 1
否则
k := i
对于 k < n 且 grid[k, j] 不等于 1，更新（k 增加 1），执行以下操作：
当 (grid[k, j] 为 2) 时，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 solve(vector<vector<int>>& 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] == 1) {
rowCnt = 0;
int k;
if (grid[i][j] == 1)
k = j + 1;
else
k = j;
for (; k < m && grid[i][k] != 1; k++) {
rowCnt += (grid[i][k] == 2);
}
}
if (!i || grid[i][j] == 1) {
colCnt[j] = 0;
int k;
if (grid[i][j] == 1)
k = i + 1;
else
k = i;
for (; k < n && grid[k][j] != 1; k++) {
colCnt[j] += (grid[k][j] == 2);
}
}
if (grid[i][j] == 0) {
ret = max(ret, rowCnt + colCnt[j]);
}
}
}
return ret;
}
};
main(){
Solution ob;
vector<vector<int>> v = {
{0,2,0,0},
{2,0,1,2},
{0,2,0,0}};
cout << (ob.solve(v));
}输入
{{0,2,0,0},
{2,0,1,2},
{0,2,0,0}}输出
3
更新于： 2020年11月10日
386 次查看
广告