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

Question

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

我们有一组图形（线、正方形、“加号”等），它们最初放置在矩阵上，因此其中一些重叠。我们正在寻找最少的移动次数，以免数字重叠。图形不沿对角线移动，仅在垂直和水平方向移动。

谢谢

Answer 1

以下是广度优先搜索解决方案的概要：

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