办法填补n×m个格子数 [英] Number of ways to fill a nxm grid

问题描述

我遇到了我的编程的书下面的问题我解决不了：

I encountered the following problem in my programming book which I could not solve:

给定一个n×m个格，写一个递归算法找出办法，这种网格可以通过3X1和1×3块需要填补的。

Given a nxm grid, write a recursive algorithm to find the number of ways that this grid could be filled by 3x1 and 1x3 blocks.

我的3×M个网格逻辑：

My logic for 3 x M grids:

查找可能被用于填充栅格的一侧M挡组合的数目

Find the number of block combinations that could be used to fill side M of the grid.

我不知道如何改变逻辑来解决上面的问题。

I do not know how to change the logic to solve the question above.

可能有人请指教？谢谢你。

Could someone please advise? Thanks.

推荐答案

让位置是左上角，和电网其后的第一个空闲插槽（左那么好吧从上到下）。最多有两种方法可以把块在现在的位置。试着将一个1×3的水平块在位置，并调用递归函数上剩余的网格。尝试把一个3X1垂直块在位置，并调用递归函数上。注意，如果有把块不合法的方式（在末尾，例如，说有只有一个2x2正方形左），该方案的这个分支未能找到解决办法。这是因为电网必须由3X1块被填充。

Let position be the upper left corner, and thereafter the first unfilled slot of the grid (left to right then top to bottom). There are up to two ways to place a block at postion. Try placing a 1x3 horizontal block at position, and call the recursive function on the remaining grid. Try placing a 3x1 vertical block at position, and call the recursive function on that. Observe that if there is no legal way to place a block (at the end, for instance, say there are is only a 2x2 square left), this branch of the program failed to find a solution. That's because the grid has to be filled by 3x1 blocks.

您的逻辑是不是递归的 - 这是一个组合的方式，试图来算。但只要一格并不大，计算机有足够的内存来实际尝试所有的组合。如果可能涉及这种方法在书中，将是巨大的递归解决其他问题。

Your logic isn't recursive - it's a combinatorial approach, trying to count. But as long a the grid isn't huge, the computer has enough memory to actually try all the combinations. If you could relate this approach to other problems solved recursively in the book that would be great.

下面的方法签名的想法

INT blockFillings（布尔[] []网格，诠释POSX，INT花束）

这篇关于办法填补n×m个格子数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！