algorithm - Given a grid, subdivide into n pieces of different shapes and sizes algorithm

Question

There's a game for iOS, Unblock Me, that takes a given grid/board and subdivides that grid into blocks of different sizes and shapes.

Could someone give me a push as to what the algorithm to accomplish such a task would look like? Given a grid, subdivide the grid into smaller pieces, like the blocks in Unblock Me but also include squares as well as rectangles. I still want to figure it out myself but I'm having some trouble getting started.

EDIT:

Also ideally the solution would leave no empty space within the original grid, it would have been subdivided in such a way that all spots are being used given a certain # of subdivisions.

Answer 1

您可以有一些标准块大小和定义的网格大小。例如，以 Unblock Me 为例：grid_size 可以是 4*4，block_size1 可以是 3*1，block_size2 可以是 2*1 等等。然后您可以定义，或者将您想要的块数作为输入网格。使用动态编程或递归回溯来用这些块填充网格。