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

สมมติว่าเรามีเมทริกซ์ m x n ชื่อ mat และจำนวนเต็ม threshold เราต้องหาความยาวด้านสูงสุดของสี่เหลี่ยมจัตุรัสที่มีผลรวมน้อยกว่าหรือเท่ากับ threshold ถ้าไม่มีสี่เหลี่ยมจัตุรัสใด ให้คืนค่า 0

ตัวอย่าง เมทริกซ์ 3x7 และ threshold = 4 ผลลัพธ์คือ 2 เพราะมีสี่เหลี่ยมจัตุรัสขนาด 2x2 ที่ผลรวม ≤ 4

ขั้นตอนการแก้ปัญหา (Prefix Sum + Binary Search)

• กำหนดเมธอด ok(x, mat, th) ตรวจสอบว่ามีสี่เหลี่ยมจัตุรัสขนาด x ที่ผลรวม ≤ th หรือไม่
  • คำนวณผลรวมสี่เหลี่ยมจัตุรัสขนาด x ทุกตำแหน่งโดยใช้ prefix sum 2D
  • ถ้าพบผลรวม ≤ th คืน true
• ในเมธอดหลัก:
  • สร้าง prefix sum 2D ของ mat
  • ค้นหาความยาวด้านสูงสุดด้วย binary search ระหว่าง 1 ถึง min(แถว, คอลัมน์)
  • ถ้า ok(mid) จริง อัปเดตคำตอบและค้นหาด้านขวา, ไม่จริงค้นหาด้านซ้าย

ตัวอย่างโค้ด (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;
        // สร้าง prefix sum แนวนอน
        for(int i = 1; i < c; i++) {
            for(int j = 0; j < r; j++) {
                mat[j][i] += mat[j][i - 1];
            }
        }
        // สร้าง prefix sum แนวตั้ง
        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;
    }
};

int 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