java - Java：多维数组中的连续区域，用于实现拉丁方

Question

我正在编写一个程序，它读取一个潜在的拉丁方格并判断它是否是一个有效的拉丁方格。现在我正在尝试判断所选区域是否是连续的。

同时读取潜在的拉丁广场和该区域的位置。该区域[0,1][0,2][1,1][1,2]将是有效区域，因为它是连续的； [0,0][0,2][1,1][1,2]不会是连续的或有效的，因为[0,0]无法到达。我如何判断它们是否连续？

Answer 1

您的问题建议至少针对不同的事情进行两次简单的检查。如果您只想检查每个点是否可以从其他每个点到达，您可以将这些点视为网络中的节点，其中 [x,y] 链接到 [x - 1, y], [x + 1, y ]、[x, y - 1] 和 [x, y + 1]。您可以使用深度优先搜索找到从给定起始节点可到达的所有节点。从任意起始节点进行这样的搜索。如果您访问所有节点，则选择的区域是连续的。我想这只是来自不同背景的洪水填充。

对于拉丁正方形，任何连续区域都可以，还是需要轴对齐的矩形？例如，如果您的相邻区域只有三个点，可以吗？如果要检查轴对齐的矩形，请计算集合中 x 和 y 的最大值和最小值，然后检查是否有每个组合 [a, b]，其中 Xmin <= a <= Xmax 和Ymin <= b <= Ymax。

Answer 2

解决这个问题的合理方法是洪水填充算法。

基本上，从您所在区域的任何点开始，并通过标记该区域中的所有邻居，然后标记该区域中尚未标记的所有邻居，在您的区域中构建一组连接到起点的位置. 当没有新的标记时，您已经找到了包含起点的最大连续区域。如果不是整个区域，则该区域不是连续的。