सी ++ में बम दुश्मन

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

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

सी ++ में बम दुश्मन

तो आउटपुट 3 होगा, जैसे हरी जगह पर बम रखने से, यह तीन दुश्मनों को मार देगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

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