# 【LeetCode】 221. Maximal Square

## Description
> Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

> 給予一個二維的二元陣列，其元素只有0和1。找到由1構成的最大正方形並回傳它的面積。

## Example:

Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

## Solution

* 先注意一件事情，他給的二元矩陣不是用`int`也不是`bool`，竟然是用`char`。(我沒注意到這個，找bug找好久QQ)
* 方法一是直接暴力破解，聽說可以過，但我沒有試過。
* 比較好的解法是使用DP。建一個表格，初始化和原來的矩陣一樣。
* 
* 畫個圖來理解一下，當紅色都是`1`，藍色都是`1`，綠色也都是`1`時，如果右下角(黃色)也是`1`，就可以變成一個大的正方形。
* 
* 換句話說，當左上、上、左都是`x`的時候，如果自己為`1`，就可以組成一個`x + 1`的正方形。
* 遞迴式：
$$
DP[i][j] =
\left\{\begin{matrix}
min(DP[i-1][j],DP[i][j-1],DP[i-1][j-1]),m[i][j]=1
\\ 0,m[i][j]=0
\end{matrix}\right.
$$
* 整理後可以發現，DP和原矩陣可以直接合併，最後時間複雜度為`O(mn)`，空間複雜度`O(1)`。

### Code

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

###### tags: `LeetCode` `C++`