সি++ এ বোমা রাখার জন্য সর্বোচ্চ সংখ্যক শত্রুকে হত্যা করা হবে?

ধরুন আমাদের তিনটি ভিন্ন মানের একটি 2D ম্যাট্রিক্স রয়েছে, 2s, 1s, এবং 0s, যেখানে একটি 2 একটি শত্রুকে প্রতিনিধিত্ব করে, 1 একটি প্রাচীরকে প্রতিনিধিত্ব করে এবং 0 একটি খালি ঘরকে উপস্থাপন করে। একটি বোমা ব্যবহার করে আমাদের সর্বোচ্চ শত্রুদের খুঁজে বের করতে হবে। বোমাটি লাগানো পয়েন্ট থেকে দেয়ালে আঘাত না হওয়া পর্যন্ত একই সারি এবং কলামে থাকা সমস্ত শত্রুদের হত্যা করে। এবং আমরা কেবল ফাঁকা জায়গায় বোমা রাখতে পারি।

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে 3, কারণ আমরা সর্বোচ্চ 3 শত্রুকে মারার জন্য সবুজ বাক্সে বোমা রাখতে পারি।

• ret :=0

• n :=গ্রিডের সারি গণনা, m :=গ্রিডের কলাম গণনা

• m

  আকারের একটি অ্যারে colCnt সংজ্ঞায়িত করুন

• আরম্ভ করার জন্য i :=0, যখন i

  • আরম্ভ করার জন্য j :=0, যখন j

    • যদি j শূন্য হয় বা গ্রিড[i, j] 1 এর মত হয়, তাহলে:

      • rowCnt :=0

      • যদি গ্রিড[i, j] 1 এর মত হয়, তাহলে:

        • k :=j + 1

      • অন্যথায়

        • k :=j

      • k

        • rowCnt :=rowCnt + 1 যখন (গ্রিড[i, k] 2 হয়), অন্যথায় 0

    • যদি i শূন্য হয় বা গ্রিড[i, j] 1 এর মত হয়, তাহলে:

      • colCnt[j] :=0

      • যদি গ্রিড[i, j] 1 এর মত হয়, তাহলে:

        • k :=i + 1

      • অন্যথায়

        • k :=i

      • k

        • colCnt[j] :=colCnt[j] + 1 যখন (গ্রিড[k, j] 2 হয়) অন্যথায় 0

    • যদি গ্রিড[i, j] 0 এর মত হয়, তাহলে:

      • ret :=ret এবং rowCnt + colCnt[j>

        এর সর্বাধিক

• রিটার্ন রিটার্ন

আরও ভালভাবে বোঝার জন্য আসুন নিম্নলিখিত বাস্তবায়ন দেখি:

উদাহরণ

#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