我在我的编程书中遇到了以下我无法解决的问题：
给定一个 nxm 网格，编写一个递归算法来找出这个网格可以被 3x1 和 1x3 块填充的方式数。
我对 3 x M 网格的逻辑：
找出可用于填充网格 M 侧的块组合的数量。
我不知道如何改变逻辑来解决上述问题。
有人可以建议吗？谢谢。
问问题
353 次
1 回答
0
让position是左上角，然后是网格的第一个未填充的插槽（从左到右然后从上到下）。最多有两种方法可以在postion. 尝试在 处放置一个 1x3 水平块position，然后在剩余的网格上调用递归函数。尝试在 处放置一个 3x1 垂直块position，并在其上调用递归函数。请注意，如果没有合法的方式来放置一个块（例如，最后，假设只剩下一个 2x2 的正方形），程序的这个分支就无法找到解决方案。那是因为网格必须由 3x1 块填充。
您的逻辑不是递归的-它是一种组合方法，试图计数。但只要网格不是很大，计算机就有足够的内存来实际尝试所有组合。如果您可以将这种方法与书中递归解决的其他问题联系起来，那就太好了。
这是方法签名的一个想法
int blockFillings(boolean[][] grid, int posx, int posy)
于 2013-11-04T02:39:23.093 回答