Vuông lớn nhất (Maximal Square) trong C++

Cho ma trận nhị phân 2D chứa '0' và '1', tìm vuông lớn nhất chỉ chứa '1' và trả về diện tích. Ví dụ ma trận 4x5 cho kết quả 4 (vuông 2x2).

Giải thuật

• ans := 0, n := số hàng, c := số cột.
• Nếu n == 0 trả về 0.
• Tạo ma trận m kích thước n x c.
• Khởi tạo m[i][j] = matrix[i][j] - '0', cập nhật ans.
• Với i từ n-2 xuống 0, j từ 1 đến c-1:
  • Nếu m[i][j] != 0: m[i][j] = 1 + min(m[i+1][j], m[i][j-1], m[i+1][j-1]).
  • Cập nhật ans = max(ans, m[i][j]).
• Trả về ans * ans.

Ví dụ mã C++

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

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int ans = 0;
        int n = matrix.size();
        if (!n) return 0;
        int c = matrix[0].size();
        vector<vector<int>> m(n, vector<int>(c));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < c; j++) {
                m[i][j] = matrix[i][j] - '0';
                ans = max(ans, m[i][j]);
            }
        for (int i = n-2; i >= 0; i--)
            for (int j = 1; j < c; j++)
                if (m[i][j]) {
                    m[i][j] = 1 + min({m[i+1][j], m[i][j-1], m[i+1][j-1]});
                    ans = max(ans, m[i][j]);
                }
        return ans * ans;
    }
};

Đầu vào

[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]

Đầu ra

4