【題目敘述】https://leetcode.com/problems/maximal-square/
【解題想法】
- 題目要求元素全為 “1” 的最大正方形面積。
- v[i][j]：存放以 (i, j) 為右下角座標看到的最大正方形邊長。
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int n = matrix.size();
if (n == 0) return 0;
int m = matrix[0].size();
if (m == 0) return 0;
vector<vector<int>> v(n);
for (int i = 0; i < n; i++){
v[i].resize(m);
}
int ans = 0;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
v[i][j] = matrix[i][j]-'0';
if (i == 0 || j == 0){
ans = max(ans, v[i][j]);
continue;
}
if (v[i][j] == 1) v[i][j] += min(v[i-1][j-1], min(v[i-1][j], v[i][j-1]));
ans = max(ans, v[i][j]);
}
}
return ans*ans;
}
};