<p>Given an <code>m x n</code> binary matrix <code>mat</code>, <em>return the number of <strong>submatrices</strong> that have all ones</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/10/27/ones1-grid.jpg" style="width: 244px; height: 245px;" />
<pre>
<strong>Input:</strong> mat = [[1,0,1],[1,1,0],[1,1,0]]
<strong>Output:</strong> 13
<strong>Explanation:</strong> 
There are 6 rectangles of side 1x1.
There are 2 rectangles of side 1x2.
There are 3 rectangles of side 2x1.
There is 1 rectangle of side 2x2. 
There is 1 rectangle of side 3x1.
Total number of rectangles = 6 + 2 + 3 + 1 + 1 = 13.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/10/27/ones2-grid.jpg" style="width: 324px; height: 245px;" />
<pre>
<strong>Input:</strong> mat = [[0,1,1,0],[0,1,1,1],[1,1,1,0]]
<strong>Output:</strong> 24
<strong>Explanation:</strong> 
There are 8 rectangles of side 1x1.
There are 5 rectangles of side 1x2.
There are 2 rectangles of side 1x3. 
There are 4 rectangles of side 2x1.
There are 2 rectangles of side 2x2. 
There are 2 rectangles of side 3x1. 
There is 1 rectangle of side 3x2. 
Total number of rectangles = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24.
</pre>

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

<ul>
	<li><code>1 &lt;= m, n &lt;= 150</code></li>
	<li><code>mat[i][j]</code> is either <code>0</code> or <code>1</code>.</li>
</ul>

class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        int ans = 0;
        int m = mat.size();
        int n = mat[0].size();
        vector<vector<int>> newmat(m + 1, vector<int>(n + 1, 0));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                newmat[i + 1][j + 1] = mat[i][j];
            }
        }
        vector<vector<int>> dp_left(m + 1, vector<int>(n + 1, 0));
        vector<vector<int>> dp_top(m + 1, vector<int>(n + 1, 0));
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (newmat[i][j] == 1) {
                    ans += 1 + dp_left[i][j - 1] + dp_top[i - 1][j];
                    dp_left[i][j] = 1 + dp_left[i][j - 1];
                    dp_top[i][j] = 1 + dp_top[i - 1][j];
                    int min_left = dp_left[i][j];
                    int min_top = dp_top[i - 1][j];
                    int x = i - 1;
                    int y = j;
                    cout << ans << " ";
                    if (newmat[i - 1][j] == 1 && newmat[i][j - 1] == 1) {
                        while (x >= 0 && newmat[x][y]) {
                            min_left=min(min_left,dp_left[x][y]);
                            if (min_left == 1)
                                break;
                            ans += min(min_left, dp_left[x][y])-1;
                            x--;
                            
                            
                        }
                        // int flag=0;
                        // while(newmat[x][y]==1 && newmat[x+1][y]==1 &&
                        // newmat[x][y+1]==1){ if(flag){
                        //     ans++;
                        //     min_top=min(dp_top[x][y],min_top);
                        //     min_left=min(dp_left[x][y],min_left);
                        //     if(min_top==1 || min_left==1)
                        //         break;
                        //     x--;
                        //     y--;
                        //     continue;
                        // }
                        // if(min(dp_top[x][y],min_top)){
                        //     ans+=min(dp_top[x][y],min_top);
                        // }
                        // if(min(dp_left[x][y],min_left)){
                        //     ans+=min(dp_left[x][y],min_left);
                        // }
                        // cout<<"sup:"<<ans<<" ";
                        // if(min(dp_left[x][y],min_left)!=0 &&
                        // min(dp_top[x][y],min_top)!=0){
                        //     ans--;
                        // }
                        // cout<<"x:"<<x<<" y:"<<y<<endl;
                        // cout<<"here:"<<ans<<" ";
                        // // if(min_top<dp_top[x][y] || min_left<dp_left[x][y])
                        // //     break;
                        // min_top=min(dp_top[x][y],min_top);
                        // min_left=min(dp_left[x][y],min_left);
                        // if(newmat[x][y]==0){
                        //     if(j-y>1){
                        //         if(newmat[x][y+1])
                        //             y++;
                        //             continue;
                        //     }
                        // }
                        // if((min_top==1 || min_left==1))
                        //     break;
                        // x--;
                        // y--;

                        // flag=1;
                        //}
                        cout << "now:" << ans << " ";
                    }
                }
            }
        }
        return ans;
    }
};
20400