資料結構
網路
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 次檢視
廣告