資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
