C++에서 합이 임계값보다 작거나 같은 정사각형의 최대 변 길이

m x n 행렬 매트와 정수 임계값이 있다고 가정합니다. 주어진 임계값보다 작거나 같은 합을 갖는 정사각형의 최대 변의 길이가 되어야 하거나 그러한 정사각형이 없으면 0을 리턴해야 합니다. 따라서 입력이 다음과 같으면 -

임계값은 4이고 한 변의 길이가 2인 정사각형이 2개 있으므로 최대값은 2이므로 출력은 2가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• ok라는 메서드를 정의합니다. x와 행렬 m, 임계값 th가 필요합니다.
• 현재 설정:=0
• i 범위 x – 1 ~ 매트 행 수 – 1
  • x – 1 범위의 c에서 매트의 열 수 – 1
    • curr :=매트[r, c]
    • c – x>=0이면 curr을 mat[r, c – x]만큼 감소
    • r – x>=0이면 mat[r - x, c]만큼 curr을 줄입니다.
    • c – x>=0이고 r – x>=0이면 mat[r – x, c - x]만큼 curr을 증가시킵니다.
    • curr <=th이면 true를 반환합니다.
• 거짓 반환
• 메인 방식에서는 행렬과 임계값이 필요합니다.
• 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
  • if 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