java - 用于比较巨大方板 (1000 x 1000) 中的坐标的数据结构

Question

我正在设计一个棋盘游戏(1000 x 1000)。董事会充满了独特的数字。我调用了一个随机数生成器，它将生成的数字与板上的数字进行比较，然后在板上划掉数字。现在每次发生这种情况时，我都必须检查整个行/列/对角线是否已被划掉，如果是，我必须进行其他操作。

不是在调用一个数字来检查行/列/对角线后每次都进行迭代，有没有办法缓存已经检查的那些，这样我就不必重复一些迭代？

Answer 1

如果我猜对了，这就是某种类似宾果游戏的游戏。

阅读上面的内容，如果您只需要检查行或列，那么拥有一个达到 1000 的迭代器将是解决方案。

但是由于您也需要检查对角线，所以不能只增加迭代器。IE：对角线可以只包含 3 个数字，并用这 3 个数字划掉，而不是 1000。

您可以使用一种算法，让您知道，对于您通过的任何位置，它的行、列和对角线是什么。

如果所有这些值都为真，则您取消了整行/列对角线。您有一个固定的 1000x1000 矩阵，因此 (int)(CalledNumber/1000)-1 是要检查的行， (CalledNumber%1000) 是列。要获得对角线，您将向上的每一行减去一列，从左到右时为向下的每一行添加一列，从右到左时反向操作。

因为那将是一个布尔 [1000][1000] 矩阵，一旦你收集了你需要的所有位置，只需将它们与 AND 条件一起检查，如果它是真的，整个行/对角线/列被划掉。

这样，您只需要检索与每个数字相关的位置，并且使用布尔值进行检查应该足够快并且不需要太多内存。

编辑：另一种可能的方式已经发布：预先计算每个对角线/行列并减少一些计数器，但我发现这有点浪费内存。

Answer 2

就在这里。但是由于 1000 并不是一个很大的数字，你可能会发现它没有必要，除非你经常这样做。我的建议是从你所拥有的开始，只有在你遇到明确的问题时才引入 这个。

我的想法是简单地计算每行、每列和对角线中未划掉的数字的数量（从这里开始，我将它们称为集合）。这些被初始化为集合的最大值，只要你划掉一个单元格（从填充到划掉），你只需减少相关的值。

考虑以下矩阵：

abc
def
ghi

当你“划掉”时f，你递减 的行计数器，递减 的def列计数器和cfi的对角计数器。行和列索引很容易计算，因为它们完全反映了您已经拥有的信息（您要划掉的单元格的行或列）。对角线索引只是稍微难一些，因为它是一个同时使用行和列的公式。bfhf

一旦您确定了给定单元格的计数器并将其递减，只需检查计数是否为零。零表示集合中的所有元素都已被划掉。

Answer 3

虽然我真的很喜欢为每列或每行设置一个简单计数器的想法，但您也可以考虑使用 BitSet。好处是，如果你真的需要，你可以找出哪些细胞仍然存在。如果这没有用，只需使用计数器。

Answer 4

您可能会发现BitSet的数组或集合很有帮助。