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

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

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

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

प्रत्येक पंक्ति और कॉलम के लिए, दीवारों के बीच के सेगमेंट में दुश्मनों की गिनती प्रीकंप्यूट करें।
rowCnt - वर्तमान पंक्ति सेगमेंट में दुश्मनों की संख्या।
colCnt[j] - कॉलम j के वर्तमान सेगमेंट में दुश्मनों की संख्या।
प्रत्येक सेल (i,j) के लिए: यदि यह खाली है (0), तो ret = max(ret, rowCnt + colCnt[j]) अपडेट करें।

उदाहरण (C++ कोड)

#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 == 0 || grid[i][j] == 1) { 
                    rowCnt = 0; 
                    int k = (grid[i][j] == 1) ? j + 1 : j; 
                    for (; k < m && grid[i][k] != 1; k++) 
                        rowCnt += (grid[i][k] == 2); 
                } 
                if (i == 0 || grid[i][j] == 1) { 
                    colCnt[j] = 0; 
                    int k = (grid[i][j] == 1) ? i + 1 : 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; 
    } 
}; 

int main() { 
    Solution ob; 
    vector<vector<int>> v = {{0,2,0,0}, {2,0,1,2}, {0,2,0,0}}; 
    cout << ob.solve(v); 
    return 0; 
}

इनपुट

{{0,2,0,0}, {2,0,1,2}, {0,2,0,0}}