C++-এ থ্রেশহোল্ডের চেয়ে কম বা সমান যোগফলযুক্ত বর্গের সর্বোচ্চ সাইড দৈর্ঘ্য

মনে করুন একটি m x n ম্যাট্রিক্স `mat` এবং একটি পূর্ণসংখ্যা `threshold` আছে। আমাদের একটি বর্গের সর্বোচ্চ সাইড-দৈর্ঘ্য বের করতে হবে যার যোগফল দেওয়া `threshold`-এর চেয়ে কম বা সমান, অথবা ০ রিটার্ন করুন যদি এমন কোনো বর্গ না থাকে। যদি ইনপুট নিচের মোতাবিক হয় -

এবং `threshold` = 4 হলে, আউটপুট হবে ২, কারণ সাইড দৈর্ঘ্য ২-এর দুটি বর্গ আছে, তাই সর্বোচ্চ ২।

এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব -

• `ok` নামক একটি মেথড সংজ্ঞায়িত করুন, এটি `x`, ম্যাট্রিক্স `m` এবং `th` নেবে
• `curr := 0` সেট করুন
• `r` = `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` রিটার্ন করুন
• মেইন মেথডে, এটি ম্যাট্রিক্স এবং `threshold` নেবে
• `r` := সারি সংখ্যা, `c` := কলাম সংখ্যা, `low := 1`, `high := min(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[i, j]`-কে `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