最大数の敵を見つけるためのプログラムは、C ++に爆弾を置くために殺されますか？

2s、1s、0sの3つの異なる値の2Dマトリックスがあるとします。ここで、2は敵を表し、1は壁を表し、0は空のセルを表します。 1つの爆弾を使って殺すことができる最大の敵を見つけなければなりません。爆弾は、植えられた地点から壁にぶつかるまで、同じ行と列にいるすべての敵を殺します。そして、爆弾は空白のスペースにしか置くことができません。

したがって、入力が次のような場合

爆弾を緑色のボックスに配置して最大3人の敵を殺すことができるため、出力は3になります。

• ret：=0

• n：=グリッドの行数、m：=グリッドの列数

• サイズmの配列列を定義します

• 初期化i：=0の場合、i

  • 初期化j：=0の場合、j

    • jがゼロまたはgrid[i、j]が1と同じ場合、次のようになります。

      • rowCnt：=0

      • grid [i、j]が1と同じ場合、次のようになります。

        • k：=j + 1

      • それ以外の場合

        • k：=j

      • k

        • rowCnt：=rowCnt + 1（grid [i、k]が2）の場合、それ以外の場合は0

    • iがゼロまたはgrid[i、j]が1と同じ場合、次のようになります。

      • colCnt [j]：=0

      • grid [i、j]が1と同じ場合、次のようになります。

        • k：=i + 1

      • それ以外の場合

        • k：=i

      • k

        • colCnt [j]：=colCnt [j] + 1（grid [k、j]が2の場合）それ以外の場合は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