C++ में थ्रेशोल्ड से कम या बराबर सम वाले वर्ग की अधिकतम साइड लंबाई

मान लीजिए हमारे पास एक m x n मैट्रिक्स mat और एक इंटीजर थ्रेशोल्ड है। हमें दिए गए थ्रेशोल्ड से कम या बराबर सम वाले वर्ग की अधिकतम साइड-लंबाई ढूंढनी है या यदि ऐसा कोई वर्ग नहीं है तो 0 लौटाएं। यदि इनपुट इस प्रकार है -

और थ्रेशोल्ड 4 है, तो आउटपुट 2 होगा, क्योंकि साइड लंबाई 2 के दो वर्ग हैं, इसलिए मैक्स 2 है।

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

• ok नामक एक मेथड परिभाषित करें, जो x, मैट्रिक्स m और थ्रेशोल्ड th लेगा
• curr := 0 सेट करें
• i के लिए x - 1 से मैट की पंक्तियों की संख्या - 1 तक की रेंज में
  • c के लिए x - 1 से मैट के कॉलम की संख्या - 1 तक की रेंज में
    • curr := mat[r, c]
    • यदि c - x >= 0, तो curr को mat[r, c - x] से घटाएं
    • यदि r - x >= 0, तो curr को mat[r - x, c] से घटाएं
    • यदि c - x >= 0 और r - x >= 0, तो curr को mat[r - x, c - x] से बढ़ाएं
    • यदि curr <= th, तो true लौटाएं
• false लौटाएं
• मेन मेथड में, यह मैट्रिक्स और थ्रेशोल्ड लेगा
• r := पंक्तियों की संख्या, c := कॉलम की संख्या, low := 1, high := r और c का मिन, ans := 0
• i के लिए 1 से c - 1 तक की रेंज में
  • j के लिए 0 से c - 1 तक की रेंज में
    • mat[j, i] को mat[j, i - 1] से बढ़ाएं
• i के लिए 1 से r - 1 तक की रेंज में
  • j के लिए 0 से c - 1 तक की रेंज में
    • mat[j, i] को mat[i - 1, j] से बढ़ाएं
• जब तक low <= high:
  • mid := low + (high - low) / 2
  • यदि ok(mid, mat, th), तो ans := mid और low := mid + 1, अन्यथा high := mid - 1
• ans लौटाएं

उदाहरण (C++)

बेहतर समझ के लिए निम्नलिखित इम्प्लीमेंटेशन देखें -

#include <bits/stdc++.h> using namespace std; typedef long long int lli; class Solution { public:    bool ok(int x, vector < vector<int> >& mat, int th){       lli current = 0;       for(int r = x - 1; r < mat.size(); r++){          for(int c = x - 1; c < mat[0].size(); c++){             current = mat[r][c];             if(c - x >= 0)current -= mat[r][c-x];             if(r -x >= 0)current -= mat[r - x][c];             if(c - x >= 0 && r - x >= 0)current += mat[r-x][c-x];             if(current <= th)return true;          }       }       return false;    }    int maxSideLength(vector<vector<int>>& mat, int th) {       int r = mat.size();       int c = mat[0].size();       int low = 1;       int high = min(r, c);       int ans = 0;       for(int i = 1; i < c; i++){          for(int j = 0; j < r; j++){             mat[j][i] += mat[j][i - 1];          }       }       for(int i = 1; i < r; i++){          for(int j = 0; j < c; j++){             mat[i][j] += mat[i - 1][j];          }       }       while(low <= high){          int mid = low + ( high - low ) / 2;          if(ok(mid, mat, th)){             ans = mid;             low = mid + 1;          }          else{             high = mid - 1;          }       }       return ans;    } }; main(){    vector<vector<int>> v = {{1,1,3,2,4,3,2},{1,1,3,2,4,3,2},{1,1,3,2,4,3,2}};    Solution ob;    cout << (ob.maxSideLength(v, 4)); }

इनपुट

[[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]] 4

आउटपुट

2