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

Question

我需要为我正在参加的 Java 课程建立一个座位系统。

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

最佳位置是指座位必须尽可能靠近彼此，并尽可能靠近中排。

现在，一些定义：

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

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

这种解决方案效率极低。有没有人有更好的主意？

Answer 1

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

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

希望有帮助。有趣的问题。