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

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

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

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

• ठीक नामक एक विधि को परिभाषित करें, इसमें x और मैट्रिक्स m और थ्रेशोल्ड वें लगेंगे
• सेट करें:=0
• i के लिए x - 1 से लेकर चटाई की पंक्तियों की संख्या - 1
  . तक
  • सी के लिए 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 वापिस करें
• झूठी वापसी
• मुख्य विधि में, यह मैट्रिक्स और थ्रेशोल्ड लेगा
• r :=पंक्तियों की संख्या, c :=स्तंभों की संख्या, निम्न :=1, उच्च :=r और c की न्यूनतम, उत्तर :=0
• i के लिए 1 से c - 1 की सीमा में
  • जे के लिए 0 से सी - 1 की सीमा में
    • चटाई बढ़ाएं[j, i] चटाई द्वारा[j, i - 1]
• i के लिए 1 से r - 1 की सीमा में
  • जे के लिए 0 से सी - 1 की सीमा में
    • चटाई बढ़ाएं[j, i] चटाई से[i-1,j]
• कम <=उच्च:
  • मध्य :=निम्न + (उच्च-निम्न)/2
  • यदि (मध्य, चटाई, वें), तो उत्तर:=मध्य और निम्न:=मध्य + 1, अन्यथा उच्च:=मध्य - 1
• वापसी उत्तर

उदाहरण(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