我想弄清楚我将如何编写算法(在 C# 中)，当给定时:
一组通常较小的基于图 block 的形状。通常是 2x2，但并非总是如此。有时形状会是 2x1 或非矩形。
一个瓦片 map (二维数组)，其中某些瓦片被标记为“免费”，某些瓦片被标记为“保留”。 free tiles 指定允许基于 tile 的形状进入的区域，保留的 tiles 不能被形状占用。
除 2x2s 之外的基于图 block 的形状示例: http://img850.imageshack.us/img850/9057/awk.png
tilemap 中“可用空间”的示例: http://img641.imageshack.us/img641/8263/spaceh.png
- 此图像中的白色指定要填充的空间，但我希望算法能够在灰色是要填充的空间而白色被保留的情况下同样有效。
基本上，算法应该将形状放置在可用空间中，并偏向顶部。它提出的解决方案不一定是“完美”的，但它应该总是能够找到存在的解决方案。此外，我真的很想避免在此算法中使用任何伪随机数。我希望它始终在给定相同输入的情况下找到相同的解决方案，即使该解决方案不是最佳解决方案。
我找到了与此相关的其他主题，但它们都与填充矩形空间而不是任意空间有关。
编辑:哦，形状可以水平和/或垂直翻转，但不能旋转。忘了提这个。
EDIT2:让我澄清一下。我不想填充空间，我想确定给定有限数量的形状应该去哪里。它们应该默认朝向顶部。
最佳答案
Knuth 写了一篇名为“Dancing Links”的论文，例如在 http://arxiv.org/pdf/cs.DS/0011047关于回溯搜索的精简版。他用它来例如用 polyonimoes 平铺平面。我的猜测是，这可以用来解决您的问题 - 需要付出一定的代价。我怀疑如果存在一种真正通用的方法来解决您的问题，它也可以应用于 Knuth 的方法，这使得它不太可能被发现。当然，你的形状比 Knuth 的更简单，所以也许有一些特定于你的问题的方法更有效。
关于c# - 用较小的基于二维图 block 的形状填充非矩形二维图 block 空间的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7265956/