我正在编写一个程序，它读取一个潜在的拉丁方格并判断它是否是一个有效的拉丁方格。现在我正在尝试判断所选区域是否是连续的。
同时读取潜在的拉丁广场和该区域的位置。该区域[0,1][0,2][1,1][1,2]将是有效区域，因为它是连续的； [0,0][0,2][1,1][1,2]不会是连续的或有效的，因为[0,0]无法到达。我如何判断它们是否连续？
问问题
914 次
2 回答
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。
于 2011-10-23T04:06:21.823 回答
1
解决这个问题的合理方法是洪水填充算法。
基本上，从您所在区域的任何点开始，并通过标记该区域中的所有邻居，然后标记该区域中尚未标记的所有邻居，在您的区域中构建一组连接到起点的位置. 当没有新的标记时，您已经找到了包含起点的最大连续区域。如果不是整个区域，则该区域不是连续的。
于 2011-10-23T01:56:36.320 回答