# POJ 1020 Anniversary Cake

This is a simple search problem. With some pruning job it’s sufficient to pass test cases.

The biggest possible area of cake is $$16 \times 10 \times 10$$, so the biggest possbile side of cake is $$40$$.

Image a cake as a matrix with rows and colums. Each element of this matrix is a 1x1 cell. The problem can be translated to if there exists a method to fill this matrix with squares.

Now fill the matrix in this order: find the lowest leftmost empty cell $$C_{i,j}$$. Find successive cells $$C_{i,j}, C_{i, j+1}, \dots, C_{i, j+w}$$ with the same height as $$C_{i,j}$$.

Choose a square and put it into an area with left upper cell as $$C_{i, j}$$. If this can not construct a solution, backtrack to use another squre, otherwise continue to the end and get a solution.

Source code in C++: