C++ में बम रखने के लिए अधिकतम संख्या में दुश्मनों को मारने का कार्यक्रम?

मान लीजिए कि हमारे पास तीन अलग-अलग मानों, 2s, 1s, और 0s का 2D मैट्रिक्स है, जहां 2 एक दुश्मन का प्रतिनिधित्व करता है, 1 एक दीवार का प्रतिनिधित्व करता है और 0 एक खाली सेल का प्रतिनिधित्व करता है। हमें एक बम का उपयोग करके अधिक से अधिक शत्रुओं को मारना है जिन्हें हम मार सकते हैं। बम सभी दुश्मनों को एक ही पंक्ति और स्तंभ में लगाए गए बिंदु से तब तक मारता है जब तक कि वह दीवार से न टकरा जाए। और हम केवल खाली जगहों पर ही बम लगा सकते हैं।

तो, अगर इनपुट पसंद है

तो आउटपुट 3 होगा, क्योंकि हम अधिकतम 3 दुश्मनों को मारने के लिए बम को हरे बॉक्स में रख सकते हैं।

रिट:=0
n :=ग्रिड की पंक्ति संख्या, m :=ग्रिड की स्तंभ संख्या
एक सरणी को परिभाषित करें colCnt आकार का m
इनिशियलाइज़ करने के लिए:=0, जब मैं
- प्रारंभ करने के लिए j :=0, जब j
  - अगर j शून्य है या ग्रिड[i, j] 1 के समान है, तो:
    - rowCnt :=0
    - अगर ग्रिड [i, j] 1 के समान है, तो:
      - कश्मीर:=जे + 1
    - अन्यथा
      - कश्मीर:=जे
    - k
      - rowCnt :=rowCnt + 1 जब (ग्रिड [i, k] 2 है), अन्यथा 0
  - अगर मैं शून्य है या ग्रिड [i, j] 1 के समान है, तो:
    - colCnt[j] :=0
    - अगर ग्रिड [i, j] 1 के समान है, तो:
      - कश्मीर:=मैं + 1
    - अन्यथा
      - कश्मीर:=मैं
    - k
      - colCnt[j] :=colCnt[j] + 1 जब (ग्रिड[k, j] 2 है) अन्यथा 0
  - अगर ग्रिड [i, j] 0 के समान है, तो:
    - 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}}