java - 如何找到矩阵中的最佳位置？

Question

我需要为我参加的 Java 类(class)构建一个座位系统。

鉴于所需的座位数量，系统需要给出大厅中的最佳位置。

我所说的最佳位置是指座位之间必须尽可能靠近，并且尽可能靠近中间一排。

现在，一些定义:

座位之间的距离 - 矩阵中分隔两个单元格的最小单元格数。例如，单元格[3,3]和[2,2]之间的距离为1。

我想过做一个递归回溯函数，它会给我一个所有可能位置的列表，然后我将遍历它，根据所有位置之间的距离和所有座位与中间行的距离对其进行分级.

此解决方案效率极低。有人有更好的主意吗？

Answer 1

我不确定 Dijkstra 在这里如何应用，除非我误解了这个问题。您的偏好是否首先是相邻座位，然后是与中间一排的距离？即假设您需要找到 5 个座位​​，并且您在第一排有五个连续的座位可用，然后在中间排有 4 个可用座位，那么我假设解决方案是在第一排选择 5 个座位​​。

因此，给定所需的座位号 N...我要做的是从中间一排开始，选择一个空座位，然后通过标记所有相邻的空座位来“扩大”一个区域。如果该区域的大小为 N，那么您就完成了。如果不是，那么我会将这个区域压入堆栈(比如“增长开始”的位置和该集群中的空座位数)。然后我会沿着中间一行标记/种植这些区域。在中间一排之后，我会向上移动一个，然后再向下移动一个。然后向上两个，向下两个，等等，直到覆盖整个矩阵。诀窍是，不断寻找空簇，直到找到一个大小为 N 的簇。如果处理整个矩阵但不存在这样的簇，则可以返回堆栈并“巧妙地”选择加起来至少为 N 的空簇.

希望对您有所帮助。有趣的问题。