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

Arnab Chakraborty

更新于： 2020年11月10日

386 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习