मान लीजिए हमारे पास एक बाइनरी मैट्रिक्स M है, हमें उस मैट्रिक्स में लगातार एक की सबसे लंबी रेखा ढूंढनी है। रेखा क्षैतिज, लंबवत, विकर्ण या प्रतिविकर्ण हो सकती है।
उदाहरण के लिए, यदि इनपुट मैट्रिक्स है:
| 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 |
| 0 | 0 | 0 | 1 |
तो आउटपुट 3 होगा।
हल करने की विधि
हम डायनामिक प्रोग्रामिंग का उपयोग करेंगे:
- ret = 0, n = पंक्तियाँ, m = स्तंभ।
- आकार n x m x 4 की 3D सरणी dp परिभाषित करें (0: लंबवत, 1: क्षैतिज, 2: विकर्ण, 3: प्रतिविकर्ण)।
- पहली पंक्ति और पहली स्तंभ के लिए प्रारंभिक मान सेट करें।
- बाकी सेल्स के लिए, चार दिशाओं में dp मान अपडेट करें।
- अधिकतम मान को ret में ट्रैक करें।
- ret लौटाएं।
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#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
