<p>Given an <code>m x n</code> binary <code>matrix</code> filled with <code>0</code>&#39;s and <code>1</code>&#39;s, <em>find the largest square containing only</em> <code>1</code>&#39;s <em>and return its area</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/26/max1grid.jpg" style="width: 400px; height: 319px;" />
<pre>
<strong>Input:</strong> matrix = [[&quot;1&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;],[&quot;1&quot;,&quot;0&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;],[&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;],[&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;]]
<strong>Output:</strong> 4
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/26/max2grid.jpg" style="width: 165px; height: 165px;" />
<pre>
<strong>Input:</strong> matrix = [[&quot;0&quot;,&quot;1&quot;],[&quot;1&quot;,&quot;0&quot;]]
<strong>Output:</strong> 1
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> matrix = [[&quot;0&quot;]]
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == matrix.length</code></li>
	<li><code>n == matrix[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 300</code></li>
	<li><code>matrix[i][j]</code> is <code>&#39;0&#39;</code> or <code>&#39;1&#39;</code>.</li>
</ul>

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        struct Field {
            int up {0};
            int left {0};
            int diag {0};
        };

        int m = matrix.size();
        int n = matrix[0].size();

        int max_edge = 0;
    
        vector<vector<Field>> fields;
        for (int i = 0; i < m; i ++) {
            fields.push_back(vector<Field>(n));
            for (int j = 0; j < n; j ++) {
                //cout << i << "," << j << endl;
                if (matrix[i][j] == '0')
                    fields[i][j].left = fields[i][j].up = 0;
                else {
                    fields[i][j].left = (i == 0 ? 1 : fields[i-1][j].left + 1);
                    fields[i][j].up = (j == 0 ? 1 : fields[i][j-1].up + 1);
                    fields[i][j].diag = min(fields[i][j].up, fields[i][j].left);
                    if (i > 0 && j > 0)
                        fields[i][j].diag = min(fields[i][j].diag, fields[i-1][j-1].diag + 1);
                    max_edge = max(max_edge, fields[i][j].diag);
                }
                //cout << " " << (char)(matrix[i][j] - '0'+' ') << fields[i][j].up << "/" << fields[i][j].left << " / " << fields[i][j].diag;
            }
            //cout << endl;
        }
        return max_edge * max_edge;
    }
};
28200