<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>

/**
    2D array to represent rectangle
    try_and_error algorithm with mutation variable to go through all possible combinations starting at the largest number.
**/

class Solution 
{

public:

    int tilingRectangle(int n, int m) 
    {
        /* 1. Determine which dimension is larger.*/
        int dimens_min = 0;
        int dimens_max = 0;
        bool row_larger_dim = false;

        if (m > n)
        {
            dimens_min = n;
            dimens_max = m;
            row_larger_dim = true;
        }
        else 
        {
            dimens_min = m;
            dimens_max = n;
        }
        
        /* 2. Find smallest number of squares needed using divide and conquer method. */
        int square_num_min = n*m;
        int half_divide = dimens_max/2;

        for (int i = dimens_max; i >= half_divide; i--)
        {
            // 1. Find dimensions of the two sub-rectangles
            int x_first = 0;
            int y_first = 0;

            int x_second = 0;
            int y_second = 0;

            if(row_larger_dim)
            {
                x_first = i;
                y_first = n;

                x_second = m - x_first;
                y_second = n;
            }
            else
            {
                x_first = m;
                y_first = i;

                x_second = m;
                y_second = n - y_first;
            }

            // 2. Find smallest number of squares required to fill each rectangles.
            bool* first_rectangle_space = new bool[x_first*y_first];
            int attempt_min = findFewestSquaresNeeded(x_first, y_first, first_rectangle_space);
            //printf(" First rectangle x: %d. y: %d. Squares needed: %d. \n", x_first, y_first, attempt_min);
            delete[] first_rectangle_space;

            if ((x_second != 0) && (y_second != 0))
            {
                bool* second_rectangle_space = new bool[x_second*y_second];
                attempt_min += findFewestSquaresNeeded(x_second, y_second, second_rectangle_space);
                //printf(" Second rectangle x: %d. y: %d. Total squares needed: %d. \n", x_second, y_second, attempt_min);
                delete[] second_rectangle_space;
            }

            // 3. Update fewest number of squares required
            if (attempt_min < square_num_min)
            {
                square_num_min = attempt_min;
            }
        }

        return square_num_min;
   }


private: 

    int findFewestSquaresNeeded(int m, int n, bool* rectangle_space)
    {
        // Find smallest dimension of this sub rectangle.
        int dimens_min = 0;

        if (m > n)
        {
            dimens_min = n;
        }
        else 
        {
            dimens_min = m;
        }

        // Find fewest squares required to fill this sub-rectangle.
        int square_num_min = n*m;

        for (int i = dimens_min; i > 0; i--)
        {
            int attempt_min = fillRectangleWithLargestSquares(m, n, rectangle_space, i);

            if (attempt_min < square_num_min)
            {
                square_num_min = attempt_min;
            }
        }
        
        return square_num_min;
    }
    /* */

    int fillRectangleWithLargestSquares(int m, int n, bool* rectangle_state, int largest_square)
    {
        /* 1. Empty the rectangle. */ 
        resetRectangleState(m, n, rectangle_state);

        /* 2. Fill the rectangle with the largest square possible. */
        int rectangle_area_max = n*m;
        int remaining_area = rectangle_area_max;
        int square_ctr = 0;
        //
        //printRectangle(m, n, rectangle_state);

        for(; remaining_area > 0;)
        {
            // Find the largest square we can fit in the rectangle
            int largest_sq_possible = addLargestSquareFitting(m, n, rectangle_state, largest_square);

            // Add this square to our rectangle
            // function to add square to the rectangle
            remaining_area -= (largest_sq_possible*largest_sq_possible);
            square_ctr++;
        }

        return square_ctr;
    }


    int addLargestSquareFitting(int m, int n, bool* rectangle_state, int square_size_max)
    {
        // Prepare data structure for our search
        bool* search_rectangle = new bool[m*n];
        resetRectangleState(m, n, search_rectangle);
        copyRectangleState(m, n, search_rectangle, rectangle_state);

        // Find largest square that can fit, and save the coordinates of its top left corner
        int largest_sq_found = 0;
        int largest_sq_x = 0;
        int largest_sq_y = 0;

        int current_sq_found = 0;
        int sq_first_col = 0;
        int sq_first_row = 0;

        int i_initial = 0;
        int i_increment = 1;
        int i_condition = m;

        int j_initial = 0;
        int j_increment = 1;
        int j_condition = n;

        // Buncha if statements
        if( search_rectangle[ index_array(0, 0, m) ] == false)
        {

        }
        else if( (search_rectangle[ index_array(m-1, 0, m) ] == false) && (m > n))
        {
            i_initial = m-1;
            i_increment = -1;
            i_condition = -1;
        }
        else if( (search_rectangle[ index_array(0, n-1, m)] == false) && (n > m))
        {
            j_initial = n-1;
            j_increment = -1;
            j_condition = -1;
        }
        else if( (search_rectangle[ index_array(m-1, n-1, m)] == false) && (m > n))
        {
            i_initial = m-1;
            i_increment = -1;
            i_condition = -1;

            j_initial = n-1;
            j_increment = -1;
            j_condition = -1;
        }


        for (int j = j_initial; !(j == j_condition); j += j_increment)
        {
            // Row by row search.
            bool investigating_empty_sq = false;

            for (int i = i_initial; !(i == i_condition); i += i_increment)
            {
                // For every element of a row.
                if (investigating_empty_sq == false)
                {
                    // An empty square was not found yet.
                    // Check if this square-unit could be the start of a new empty square.
                    if(search_rectangle[ index_array(i, j, m) ] == false)
                    {
                        // We found an empty square-unit. Start empty square search.
                        investigating_empty_sq = true;
                        current_sq_found = 0;
                        sq_first_col = i;
                        sq_first_row = j;
                    }
                }

                // Found an empty square, see if there is space to make it larger.
                bool height_violation = (j + (current_sq_found*j_increment)) == j_condition;
                bool out_of_bounds =  height_violation || (current_sq_found >= square_size_max);
                bool no_space_found = false;

                if (investigating_empty_sq && !out_of_bounds)
                {
                    // There is potential for this square to grow larger.
                    int max_height = j + (current_sq_found*j_increment) + j_increment;
                    int max_height_index = max_height - j_increment;

                    // Search if potential new column is empty.
                    for (int y = j; !(y == max_height) && (!no_space_found); y += j_increment)
                    {
                        no_space_found |= search_rectangle[ index_array(i, y, m) ];
                    }
                    
                    // Search if potential new row is empty.
                    for (int x = sq_first_col; !(x == i) && (!no_space_found); x += i_increment)
                    {
                        no_space_found |= search_rectangle[ index_array(x, max_height_index, m) ];
                    }

                    if (!no_space_found)
                    {
                        // Success, we found room for a larger square.
                        for (int y = j; !(y == max_height); y += j_increment)
                        {
                            search_rectangle[ index_array(i, y, m) ] = true;
                        }

                        for (int x = sq_first_col; !(x == i); x += i_increment)
                        {
                            search_rectangle[ index_array(x, max_height_index, m) ] = true;
                        }

                        current_sq_found++;
                    }
                }

                // Check if this square has achieved maximum size.
                bool end_of_row_reached = ((i + i_increment) == i_condition);
                bool max_size_achieved = end_of_row_reached || out_of_bounds || no_space_found;

                if (max_size_achieved && investigating_empty_sq)
                {
                    // We haven't found additional space to enlarge the square. 
                    // Check if this is the largest square found.
                    if(current_sq_found > largest_sq_found)
                    {
                        largest_sq_found = current_sq_found;
                        largest_sq_x = sq_first_col;
                        largest_sq_y = sq_first_row;
                    }

                    if(largest_sq_found >= square_size_max)
                    {
                        break;
                    }

                    investigating_empty_sq = false;
                }
            }
        }

        // Add largest square to the triangle.
        int max_width = largest_sq_x + (largest_sq_found*i_increment);
        int max_height = largest_sq_y + (largest_sq_found*j_increment);
        printf(" first x: %d, first y: %d, square size: %d. \n", largest_sq_x, largest_sq_y, largest_sq_found);

        for (int b = largest_sq_y; !(b == max_height); b += j_increment)
        {
            for (int a = largest_sq_x; !(a == max_width); a += i_increment)
            {
                rectangle_state[ index_array( a, b, m) ] = true;
            }
        }

        //
        //printRectangle(m, n, rectangle_state);

        // Clean up memory
        delete[] search_rectangle;

        // Return size of square that was added.
        return largest_sq_found;
    }


    void copyRectangleState(int m, int n, bool* dest_rectangle, bool* src_rectangle)
    {
        for (int j = 0; j < n; j++)
        {
            for (int i = 0; i < m; i++)
            {
                int index = index_array(i, j, m);
                dest_rectangle[index] = src_rectangle[index];
            }
        }
    }


    void resetRectangleState(int m, int n, bool* rectangle_state)
    {
        for (int j = 0; j < n; j++)
        {
            for(int i = 0; i < m; i++)
            {
                rectangle_state[ index_array(i, j, m) ] = false;
            }
        }
    }


    int index_array(int x, int y, int row_size)
    {
        return (x + y*row_size);
    }


    void printRectangle(int m, int n, bool* rectangle_status)
    {
        printf(" Print Rectangle status:\n");
        
        for (int j = 0; j < n; j++)
        {
            printf(" [");
            for(int i = 0; i < m; i++)
            {
                if(rectangle_status[ index_array(i, j, m) ])
                {
                    printf(" 1");
                }
                else 
                {
                    printf(" 0");
                }
            }
            printf(" ]\n");
        }
    }

};
12000