Độ dài cạnh tối đa của vuông có tổng ≤ ngưỡng trong C++

Cho ma trận m x n mat và số nguyên threshold. Tìm độ dài cạnh lớn nhất của hình vuông có tổng phần tử ≤ threshold, trả về 0 nếu không có.

Ví dụ ma trận 3x7, threshold = 4. Kết quả: 2 (có vuông 2x2 tổng ≤ 4).

Giải thuật (Tiền tố 2D + Tìm kiếm nhị phân)

1. Xây dựng ma trận tiền tố 2D: cộng dọc hàng, rồi cộng dọc cột.
2. Hàm ok(x) kiểm tra có vuông cạnh x tổng ≤ th:
3. Duyệt góc dưới phải của vuông x, tính tổng bằng công thức bao hàm - loại trừ.
4. Nếu tìm thấy tổng ≤ th, trả về true.
5. Tìm kiếm nhị phân low=1, high=min(m,n) để tìm x lớn nhất thỏa mãn.

Ví dụ 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(), c = mat[0].size();
        int low = 1, high = min(r, c), 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;
    }
};

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));
    return 0;
}

Đầ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