C++ में बम एनिमी - अधिकतम दुश्मनों को मारने का स्थान खोजें

समस्या विवरण

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

उदाहरण के लिए, यदि इनपुट इस तरह का ग्रिड है:

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

समाधान दृष्टिकोण

प्रीकंप्यूटेशन के साथ O(mn) समय में:

1. ret := 0
2. n := ग्रिड की पंक्ति संख्या, m := स्तंभ संख्या
3. आकार m की सरणी colCnt परिभाषित करें
4. प्रत्येक सेल (i, j) के लिए:
   • पंक्ति गणना (rowCnt) की गणना करें - बाएं/दाएं दीवार तक दुश्मन
   • स्तंभ गणना (colCnt[j]) की गणना करें - ऊपर/नीचे दीवार तक दुश्मन
   • यदि ग्रिड[i][j] == '0', तो ret = max(ret, rowCnt + colCnt[j]) अपडेट करें
5. ret लौटाएं

C++ कार्यान्वयन

#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; 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<vector<char>> v = {{'0','E','0','0'},{'E','0','W','E'},{'0','E','0','0'}}; 
    cout << (ob.maxKilledEnemies(v)); 
    return 0;
}

इनपुट

{{'0','E','0','0'},{'E','0','W','E'},{'0','E','0','0'}}

आउटपुट

3