合計がC++のしきい値以下の正方形の最大辺の長さ

mxn行列マットと整数しきい値があるとします。合計が指定されたしきい値以下の正方形の最大辺の長さにする必要があります。そのような正方形がない場合は0を返します。したがって、入力が-

また、しきい値は4で、出力は2になります。これは、辺の長さが2の正方形が2つあるため、最大値が2です

これを解決するには、次の手順に従います-

• okというメソッドを定義します。これにはxと行列mおよびしきい値thが必要です
• set curr：=0
• 範囲x– 1からマットの行数–1
  のiの場合
  • 範囲x– 1からマットの列数–1のcの場合
    • 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
• 1からc–1の範囲のiの場合
  • 0からc–1の範囲のjの場合
    • mat [j、i]をmat [j、i-1]で増やします
• 1からr–1の範囲のiの場合
  • 0からc–1の範囲のjの場合
    • mat [j、i]をmat [i-1、j]で増やします
• 低い<=高い：
  • 中：=低+（高-低）/ 2
  • of（mid、mat、th）の場合、ans：=midおよびlow：=mid + 1、それ以外の場合はhigh：=mid – 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