Chương trình tìm kích thước lớn nhất của ma trận con vuông cùng giá trị trong C++

Mô tả bài toán

Cho một ma trận 2D, tìm giá trị k lớn nhất sao cho tồn tại một ma trận con k×k mà tất cả các phần tử đều có cùng giá trị.

Ví dụ: với ma trận

1 1 8 3
1 5 5 5
2 5 5 5
4 5 5 5

Kết quả là 3, vì tồn tại ma trận con 3×3 toàn giá trị 5.

Giải thuật

1. n := số hàng, m := số cột của ma trận.
2. Khởi tạo mảng dp[n][m] toàn giá trị 1.
3. ret := 1.
4. Duyệt i từ n-1 xuống 0, j từ m-1 xuống 0:
   • val := INF.
   • Nếu i+1 < n và v[i+1][j] == v[i][j] thì val = min(dp[i+1][j], val), ngược lại val = 0.
   • Nếu j+1 < m và v[i][j+1] == v[i][j] thì val = min(dp[i][j+1], val), ngược lại val = 0.
   • Nếu i+1 < n, j+1 < m và v[i+1][j+1] == v[i][j] thì val = min(dp[i+1][j+1], val), ngược lại val = 0.
   • Nếu val == INF thì bỏ qua.
   • dp[i][j] += val; ret = max(ret, dp[i][j]).
5. Trả về ret.

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int solve(vector<vector<int>>& v) {
        int n = v.size();
        int m = v[0].size();
        vector<vector<int>> dp(n, vector<int>(m, 1));
        int ret = 1;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                int val = INT_MAX;
                if (i + 1 < n && v[i + 1][j] == v[i][j]) {
                    val = min(dp[i + 1][j], val);
                } else {
                    val = 0;
                }
                if (j + 1 < m && v[i][j + 1] == v[i][j]) {
                    val = min(dp[i][j + 1], val);
                } else {
                    val = 0;
                }
                if (i + 1 < n && j + 1 < m && v[i + 1][j + 1] == v[i][j]) {
                    val = min(dp[i + 1][j + 1], val);
                } else {
                    val = 0;
                }
                if (val == INT_MAX) continue;
                dp[i][j] += val;
                ret = max(ret, dp[i][j]);
            }
        }
        return ret;
    }
};

int solve(vector<vector<int>>& matrix) {
    return (new Solution())->solve(matrix);
}

int main() {
    vector<vector<int>> matrix = {
        {1, 1, 8, 3},
        {1, 5, 5, 5},
        {2, 5, 5, 5},
        {4, 5, 5, 5}
    };
    cout << solve(matrix);
    return 0;
}

Đầu vào

{{1, 1, 8, 3}, {1, 5, 5, 5}, {2, 5, 5, 5}, {4, 5, 5, 5}}

Đầu ra

3