<p>Given a rectangle of size <code>n</code> x <code>m</code>, return <em>the minimum number of integer-sided squares that tile the rectangle</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2019/10/17/sample_11_1592.png" style="width: 154px; height: 106px;" /></p>

<pre>
<strong>Input:</strong> n = 2, m = 3
<strong>Output:</strong> 3
<strong>Explanation:</strong> <code>3</code> squares are necessary to cover the rectangle.
<code>2</code> (squares of <code>1x1</code>)
<code>1</code> (square of <code>2x2</code>)</pre>

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

<p><img alt="" src="https://assets.leetcode.com/uploads/2019/10/17/sample_22_1592.png" style="width: 224px; height: 126px;" /></p>

<pre>
<strong>Input:</strong> n = 5, m = 8
<strong>Output:</strong> 5
</pre>

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

<p><img alt="" src="https://assets.leetcode.com/uploads/2019/10/17/sample_33_1592.png" style="width: 224px; height: 189px;" /></p>

<pre>
<strong>Input:</strong> n = 11, m = 13
<strong>Output:</strong> 6
</pre>

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

<ul>
	<li><code>1 &lt;= n, m &lt;= 13</code></li>
</ul>

class Solution {
public:
    int ans;
    void dfs(int n, int m, int ct, vector<vector<bool>> &occ){
        if(ct>=ans) return;
        for(int r=0; r<n; r++){
            for(int c=0; c<m; c++){
                if(occ[r][c]) continue;
                int sqlen=min(n,m);
                int i=1;
                while(r+i-1<n && occ[r+i-1][c]==0) i++; //vertically
                sqlen=min(sqlen,i-1);
                i=1;
                while(c+i-1<m && occ[r][c+i-1]==0) i++; //horizontally
                sqlen=min(sqlen,i-1);
                while(sqlen){
                    for(int row=r; row<r+sqlen; row++)
                        for(int col=c; col<c+sqlen; col++) occ[row][col]=true;
                    dfs(n,m,ct+1,occ);
                    for(int row=r; row<r+sqlen; row++)
                        for(int col=c; col<c+sqlen; col++) occ[row][col]=false;
                    sqlen--;
                }
                return;
            }
        }
        ans=min(ans,ct);
    }

    int tilingRectangle(int n, int m) {
        vector<vector<bool>> occ(n,vector<bool> (m,false));
        ans=n*m;
        dfs(n,m,0,occ);
        return ans;
    }
};
9000