方阵上的最优数字排列
本文关键字：数字 排列 方阵 | 更新日期: 2023-09-27 18:11:04
我正在尝试解决以下问题，但不知道如何解决:
我们有一组图形(直线、正方形、"+"等)，它们最初被放置在一个矩阵上，因此它们中的一些重叠。我们正在寻找最少的移动次数，这样数字就不会重叠。数字不能沿对角线移动，只能垂直和水平移动。
谢谢
下面是宽度优先搜索解决方案的概要:
- 假设一个(隐式)图由顶点组成，每个顶点代表一个唯一的位置矩阵中的所有图形，其中边表示单个的合法移动图形(上/下/左/右，不导致图形移动到矩阵外)。
- 通过将表示初始图形配置的节点添加到标记为未访问的BFS队列，在此图中执行广度优先搜索。
- 对于队列中的每个未访问节点，检查它是否无重叠，如果是，则完成，如果不是，将其标记为已访问，并将其邻居(所有可能的一步移动的所有数字从该配置)添加到BFS队列的末尾。你可以使用HashSet来存储你访问过的节点(图形位置的唯一配置)，因为通过不同的移动序列可以达到相同的配置。
- 如果BFS队列变为空，则没有解决方案，因为您已经检查了所有可能的图形配置。