Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 221. Maximal Square

---

參考資訊：
https://www.cnblogs.com/grandyang/p/4550604.html

題目：


解答：

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        int ans = 0;

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == '0') {
                    continue;
                }

                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                }
                else {
                    dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
                }
                ans = max(ans, dp[i][j]);
            }
        }

        return ans * ans;
    }
};