Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 4.
LeetCode上的原题，请参见我之前的博客Maximal Square。
解法一：
class Solution { public: /** * @param matrix: a matrix of 0 and 1 * @return: an integer */ int maxSquare(vector<vector<int> > &matrix) { if (matrix.empty() || matrix[0].empty()) return 0; int m = matrix.size(), n = matrix[0].size(), res = 0; vector<vector<int>> sum = matrix; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { int t = sum[i][j]; if (i > 0) t += sum[i - 1][j]; if (j > 0) t += sum[i][j - 1]; if (i > 0 && j > 0) t -= sum[i - 1][j - 1]; sum[i][j] = t; int cnt = 1; for (int k = min(i, j); k >= 0; --k) { int d = sum[i][j]; if (i - cnt >= 0) d -= sum[i - cnt][j]; if (j - cnt >= 0) d -= sum[i][j - cnt]; if (i - cnt >= 0 && j - cnt >= 0) d += sum[i - cnt][j - cnt]; if (d == cnt * cnt) res = max(res, d); ++cnt; } } } return res; } };
本文转自博客园Grandyang的博客，原文链接：最大正方形[LintCode] Maximal Square ，如需转载请自行联系原博主。