C++ এ বোমা শত্রু

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

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

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

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• ret :=0

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

• m

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

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

  • j শুরু করার জন্য :=0, যখন j করুন

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

      • rowCnt :=0

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

        • k :=j + 1

      • অন্যথায়

        • k :=j

      • k

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

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

      • colCnt[j] :=0

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

        • k :=i + 1

      • অন্যথায়

        • k :=i

      • k

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

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

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

        এর সর্বাধিক

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

উদাহরণ

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

#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