ความยาวด้านสูงสุดของสี่เหลี่ยมจัตุรัสโดยมีผลรวมน้อยกว่าหรือเท่ากับเกณฑ์ใน C++

สมมติว่าเรามีเมทริกซ์ m x n และขีดจำกัดจำนวนเต็ม เราต้องมีความยาวด้านสูงสุดของสี่เหลี่ยมจัตุรัสโดยมีผลรวมน้อยกว่าหรือเท่ากับเกณฑ์ที่กำหนดหรือคืนค่า 0 หากไม่มีสี่เหลี่ยมจัตุรัสดังกล่าว ดังนั้นหากอินพุตเป็นแบบ −

และขีดจำกัดคือ 4 จากนั้นเอาต์พุตจะเป็น 2 เนื่องจากมีความยาวด้าน 2 กำลังสองสี่เหลี่ยม ดังนั้นค่าสูงสุดคือ 2

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดวิธีการที่เรียกว่า ตกลง จะใช้ x และเมทริกซ์ m และขีดจำกัด th
• กำหนดสกุลเงิน :=0
• สำหรับ i ในช่วง x – 1 ถึงจำนวนแถวของ mat – 1
  • สำหรับ c ในช่วง x – 1 ถึงจำนวน cols ของ mat – 1
    • curr :=mat[r, c]
    • ถ้า c – x>=0 ให้ลดสกุลเงินโดย mat[r, c – x]
    • ถ้า r – x>=0 ให้ลดสกุลเงินโดย mat[r - x, c]
    • ถ้า c – x>=0 และ r – x>=0 ให้เพิ่มสกุลเงินโดย mat[r – x, c - x]
    • ถ้า curr <=th แล้วคืนค่าเป็น true
• คืนค่าเท็จ
• ในวิธีหลัก จะใช้เมทริกซ์และขีดจำกัด
• r :=จำนวนแถว, c :=จำนวนคอลัมน์, ต่ำ :=1, สูง :=ต่ำสุดของ r และ c, ans :=0
• สำหรับ i ในช่วง 1 ถึง c – 1
  • สำหรับ j ในช่วง 0 ถึง c – 1
    • เพิ่ม mat[j, i] โดย mat[j, i - 1]
• สำหรับฉันอยู่ในช่วง 1 ถึง r – 1
  • สำหรับ j ในช่วง 0 ถึง c – 1
    • เพิ่ม mat[j, i] โดย mat[ i - 1,j]
• ในขณะที่ต่ำ <=สูง:
  • กลาง :=ต่ำ + (สูง - ต่ำ) / 2
  • if of(mid, mat, th) แล้ว ans :=mid and 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