c++ - block 拼图求解C++算法

Question

我想制定一个算法来解决 Block Puzzles , 但尽可能高效。我已经做了简单的方法(回溯)。

我将所有内容都表示为矩阵 - block 必须适合的大矩阵在开始时全部为 0，并且 block 是矩阵，如果空间已满则为 1，如果空间为空则为 0。现在下一个可能更有效的想法是在转到下一行之前始终验证一行是否完整。我的意思是我可能有一 block 表示为
0 1 0<br/>
1 1 1<br/>
0 1 0(穿过)。如果十字放在角落里，程序将无用地为无效解决方案进行整个回溯，因此它应该返回并尝试另一 block 。

如果有必要，我可以提供一段代码，正如我所说，我只是做了简单的低效回溯。
有没有人有更好的想法？在这种情况下可以使用动态规划吗？

Answer 1

将问题想象成一个图:节点是方 block 排列的各种状态，边是从一个节点到另一个节点的可能移动。那么解就是当前位置到目标的最短距离，可以用Dijkstra算法计算。