C++ में मैट्रिक्स में लगातार एक की सबसे लंबी लाइन

मान लीजिए कि हमारे पास एक बाइनरी मैट्रिक्स एम है, हमें उस मैट्रिक्स में लगातार एक की सबसे लंबी लाइन ढूंढनी है। रेखा क्षैतिज, लंबवत, विकर्ण या विरोधी विकर्ण हो सकती है।

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

तो आउटपुट 3

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

• रिट:=0

• n :=M की पंक्ति

• एम :=एम का कॉलम

• क्रम n x m x 4 के एक 3D सरणी dp को परिभाषित करें

• इनिशियलाइज़ करने के लिए मैं :=0, जब i

  • इनिशियलाइज़ j :=0 के लिए, जब j <4, अपडेट करें (j को 1 से बढ़ाएँ), करें -

    • डीपी [0, आई, जे]:=एम [0, आई]

    • ret :=अधिकतम रिट और dp[0, i, j]

• इनिशियलाइज़ j :=0 के लिए, जब j

  • यदि M[0, j] शून्य नहीं है और j> 0 है, तो -

    • डीपी [0, जे, 1]:=1 + डीपी [0, जे - 1, 1]

    • रिट:=अधिकतम रिट और डीपी [0, जे, 1]

• इनिशियलाइज़ करने के लिए मैं :=1, जब i

  • इनिशियलाइज़ j :=0 के लिए, जब j

    • dp[i, j, 0] :=(यदि M[i, j] गैर-शून्य है, तो 1 + dp[i - 1, j, 0], अन्यथा 0)

    • अगर j> 0, तो -

      • dp[i, j, 1] :=(यदि M[i, j] गैर-शून्य है, तो dp[i, j - 1, 1] + 1, अन्यथा 0)

      • dp[i, j, 2] :=(यदि M[i, j] गैर-शून्य है, तो dp[i - 1, j-1, 2] + 1, अन्यथा 0)

    • अन्यथा

      • dp[i, j, 1] :=M[i, j]

      • dp[i, j, 2]:=M[i, j]

    • यदि j + 1

      • dp[i, j, 3] :=(यदि M[i, j] गैर-शून्य है, तो dp[i - 1, j + 1, 3] + 1, अन्यथा 0)

    • अन्यथा

      • डीपी [आई, जे, 3]:=एम [आई, जे]

    • इनिशियलाइज़ k :=0 के लिए, जब k <4, अपडेट करें (1 से k बढ़ाएँ), करें -

      • ret :=अधिकतम रिट और dp[i, j, k]

• वापसी रिट

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int longestLine(vector<vector<int>>& M) {
      int ret = 0;
      int n = M.size();
      int m = !n ? 0 : M[0].size();
      vector<vector<vector<int> > > dp(n, vector<vector<int> >(m, vector<int>(4)));
      for (int i = 0; i < m; i++) {
         for (int j = 0; j < 4; j++) {
            dp[0][i][j] = M[0][i];
            ret = max(ret, dp[0][i][j]);
         }
      }
      for (int j = 0; j < m; j++) {
         if (M[0][j] && j > 0) {
            dp[0][j][1] = 1 + dp[0][j - 1][1];
            ret = max(ret, dp[0][j][1]);
         }
      }
      for (int i = 1; i < n; i++) {
         for (int j = 0; j < m; j++) {
            dp[i][j][0] = M[i][j] ? 1 + dp[i - 1][j][0] : 0;
            if (j > 0) {
               dp[i][j][1] = M[i][j] ? dp[i][j - 1][1] + 1 : 0;
               dp[i][j][2] = M[i][j] ? dp[i - 1][j - 1][2] + 1 : 0;
            }
            else {
               dp[i][j][1] = M[i][j];
               dp[i][j][2] = M[i][j];
            }
            if (j + 1 < m) {
               dp[i][j][3] = M[i][j] ? dp[i - 1][j + 1][3] + 1 : 0;
            }
            else {
               dp[i][j][3] = M[i][j];
            }
            for (int k = 0; k < 4; k++) {
               ret = max(ret, dp[i][j][k]);
            }
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,1,1,0},{0,1,1,0},{0,0,0,1}};
   cout << (ob.longestLine(v));
}

इनपुट

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

आउटपुट

3