বম বLAST করিয়ে সর্বোচ্চ শত্রু ধ্বংস C++-এ

একটি ২D ম্যাট্রিক্সে ২ = শত্রু, ১ = দেওয়াল, ০ = খালি সেল। একটি বম শুধু খালি সেলে রাখা যায়। বম একই সারি ও কলামের সব শত্রুকে ধ্বংস করে যতক্ষণ না দেওয়াল পায়। সর্বোচ্চ কতজন শত্রু ধ্বংস করা যায় তা বের করতে হবে।

উদাহরণ

ম্যাট্রিক্স:

0 2 0 0
2 0 1 2
0 2 0 0

আউটপুট: 3 (হরিট বক্সে বম রাখলে ৩ জন শত্রু মরে)

অ্যালগরিদম (O(n×m) প্রি-কম্পিউটেশন)

প্রতিটি সেলের জন্য সারি ও কলামে দেওয়াল না পাওয়া পর্যন্ত শত্রুর সংখ্যা প্রি-কম্পিউট করুন।
rowCnt = বর্তমান সারি সেগমেন্টে শত্রু সংখ্যা।
colCnt[j] = বর্তমান কলাম সেগমেন্টে শত্রু সংখ্যা।
প্রতিটি খালি সেল (০) এর জন্য rowCnt + colCnt[j] ক্যালকুলেট করুন এবং সর্বোচ্চ মান রাখুন।

C++ কোড উদাহরণ

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int maxKilledEnemies(vector>& grid) {
        int n = grid.size();
        if (n == 0) return 0;
        int m = grid[0].size();
        
        int ret = 0;
        int rowCnt = 0;
        vector colCnt(m, 0);
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // Row count update
                if (j == 0 || grid[i][j-1] == 1) {
                    rowCnt = 0;
                    for (int k = j; k < m && grid[i][k] != 1; k++)
                        rowCnt += (grid[i][k] == 2);
                }
                
                // Col count update
                if (i == 0 || grid[i-1][j] == 1) {
                    colCnt[j] = 0;
                    for (int k = i; 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> v = {
        {0, 2, 0, 0},
        {2, 0, 1, 2},
        {0, 2, 0, 0}
    };
    cout << ob.maxKilledEnemies(v);
    return 0;
}

ইনপুট

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