c# - 方阵上的最佳图形排列

Question

我正在尝试解决以下问题，但想不出如何解决:

我们有一组图形(直线、正方形、“加号”等)，它们最初被放置在一个矩阵上，因此它们中的一些重叠。我们正在寻找最少数量的移动，以便数字不重叠。图形不会沿对角线移动，只会垂直和水平移动。

谢谢

Answer 1

这是 breadth-first search 的大纲解决方案:

• 假设一个 ( implicit ) 图由顶点组成，每个顶点代表矩阵中的所有数字以及边缘代表单个合法移动图(上/下/左/右不会导致图形移出矩阵)。
• 通过将表示初始图形配置的节点添加到标记为未访问的 BFS 队列，对该图执行广度优先搜索。
• 对于队列中的每个未访问节点，检查它是否无重叠，如果是，你就完成了，如果不是，则将其标记为已访问并添加其邻居(该配置中所有图形的所有可能的一步移动) 到 BFS 队列的末尾。您可以使用 HashSet 来存储您访问过的节点(图形位置的独特配置)，因为可以通过不同的移动序列达到相同的配置。
• 如果 BFS 队列变空，则没有解决方案，因为您已经检查了所有可能的图形配置。