Chiều dài cạnh tối đa của hình vuông có tổng nhỏ hơn hoặc bằng ngưỡng trong C ++

Giả sử chúng ta có một ma trận m x n và một ngưỡng số nguyên. Chúng ta có độ dài cạnh tối đa của hình vuông có tổng nhỏ hơn hoặc bằng ngưỡng đã cho hoặc trả về 0 nếu không có hình vuông nào như vậy. Vì vậy, nếu đầu vào giống như -

Và ngưỡng là 4, thì đầu ra sẽ là 2, vì có hai hình vuông có độ dài cạnh là 2, vì vậy tối đa là 2

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một phương thức được gọi là ok, phương thức này sẽ lấy x và ma trận m và ngưỡng thứ
• set curr:=0
• cho tôi trong phạm vi x - 1 đến số hàng của thảm - 1
  • cho c trong phạm vi x - 1 đến số cols của mat - 1
    • curr:=mat [r, c]
    • nếu c - x> =0, thì giảm curr theo mat [r, c - x]
    • nếu r - x> =0, sau đó giảm curr theo mat [r - x, c]
    • nếu c - x> =0 và r - x> =0, thì tăng curr theo mat [r - x, c - x]
    • nếu curr <=th, thì trả về true
• trả về false
• Trong phương thức chính, nó sẽ lấy ma trận và ngưỡng
• r:=số hàng, c:=số cột, thấp:=1, cao:=tối thiểu của r và c, ans:=0
• cho tôi trong phạm vi từ 1 đến c - 1
  • cho j trong phạm vi từ 0 đến c - 1
    • tăng mat [j, i] bởi mat [j, i - 1]
• cho tôi trong phạm vi từ 1 đến r - 1
  • cho j trong phạm vi từ 0 đến c - 1
    • tăng mat [j, i] bởi mat [i - 1, j]
• trong khi thấp <=cao:
  • giữa:=low + (cao - thấp) / 2
  • if of (mid, mat, th), then ans:=mid and low:=mid + 1, ngược lại high:=mid - 1
• trả lại ans

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

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

Đầu ra

2