ম্যাট্রিক্সে সর্বদীর্ঘ কনsekutিভ ১-র লাইন C++-এ

সমস্যা বিবরণ

একটি বাইনারি ম্যাট্রিক্স দেওয়া আছে। সেটিতে সারি (horizontal), কলাম (vertical), ডায়াগোনাল বা অ্যান্টি-ডায়াগোনাল — যেকোনো দিকের সর্বদীর্ঘ কনsekutিভ ১-র লাইন দৈর্ঘ্য বের করতে হবে।

উদাহরণ

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

0 1 1 0
0 1 1 0
0 0 0 1

অ্যালগরিদম: ৩D DP

dp[i][j][k] = সেল (i,j) এ শেষ হওয়া দিক k-এ কনsekutিভ ১-এর দৈর্ঘ্য।
k=0: ভার্টিক্যাল, k=1: হরিজন্টাল, k=2: ডায়াগোনাল, k=3: অ্যান্টি-ডায়াগোনাল।

রিকারেন্স:

• dp[i][j][0] = M[i][j] ? 1 + dp[i-1][j][0] : 0
• dp[i][j][1] = M[i][j] ? 1 + dp[i][j-1][1] : 0
• dp[i][j][2] = M[i][j] ? 1 + dp[i-1][j-1][2] : 0
• dp[i][j][3] = M[i][j] ? 1 + dp[i-1][j+1][3] : 0

প্রতিটি সেলে ৪ দিক চেক করে গ্লোবাল ম্যাক্স আপডেট করুন।

C++ বাস্তবায়ন

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

class Solution {
public:
    int longestLine(vector<vector<int>>& M) {
        int n = M.size();
        if (n == 0) return 0;
        int m = M[0].size();
        vector<vector<array<int,4>>> dp(n, vector<array<int,4>>(m, {0,0,0,0}));
        int ans = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (M[i][j] == 0) continue;
                dp[i][j][0] = 1 + (i > 0 ? dp[i-1][j][0] : 0);
                dp[i][j][1] = 1 + (j > 0 ? dp[i][j-1][1] : 0);
                dp[i][j][2] = 1 + (i > 0 && j > 0 ? dp[i-1][j-1][2] : 0);
                dp[i][j][3] = 1 + (i > 0 && j+1 < m ? dp[i-1][j+1][3] : 0);
                for (int k = 0; k < 4; k++)
                    ans = max(ans, dp[i][j][k]);
            }
        }
        return ans;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{0,1,1,0},{0,1,1,0},{0,0,0,1}};
    cout << ob.longestLine(v); // আউটপুট: 3
    return 0;
}

ইনপুট ও আউটপুট

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(n × m) — প্রতিটি সেল একবার।
• স্থান জটিলতা: O(n × m) — DP টেবিল (O(m)-এও করা যায়)।