0

对于那些不知道宾果游戏的人来说，它的玩法如下

1）您得到一张 BINGO 卡，其中有一个随机打印的 NXN 数字矩阵。数字是唯一的。打印的最大数字可以大于 N^2。例如，如果您有 5x5 矩阵，那么最大数字也可以是 75。但是数字的范围是预先确定的，例如 1 到 M。

2) 一个人随机说出 1 到 M 范围内的数字。

3）如果号码在你的卡上，你划掉号码。

4）重复数字交叉的过程。当你穿过一整行或整列或两条对角线时，你就得到了你的第一个宾果游戏仍然继续，因为可能的宾果总数为 N+N+2 N行，N 列和 2 条对角线。

现在我想为它创建一个算法。用户将输入随机数，算法将听到它们并在矩阵中交叉它的数字（已经提供）。一旦它得到 BINGO，它就会声明它。最好的方法是什么

我尝试将其作为卡的二维矩阵

当一个数字被宣布时，我会在 O(NxN) 时间内搜索它。当我找到它时，我将它设为 0。

将其设为0后，我搜索相应的行和列现在是否全为零。如果它在对角线上，我也搜索对角线。它需要O（3N）时间。

有更好的方法吗？

4

3 回答 3

0

您可以为将映射到一对（行、列）的每个数字形成一个映射。

if ( myMap[number] exists ) {
  then increment rowCount[ myMap[number].row ];
  then increment columnCount[ myMap[number].column ];
}

if ( rowCount[myMap[number].row] == N ) { bingo! }
if ( columnCount[myMap[number].column] == N ) { bingo! }

myMap.erase( number );

对角线也是如此。

于 2013-10-26T12:48:39.930 回答
0

使用数组存储卡上的数字并保持排序。呼叫号码后，使用二进制搜索（O（logN）时间）搜索号码。这应该是一种快速的方法。

于 2014-06-08T22:42:49.393 回答
0

创建一个在宾果卡中保存 x 和 y 位置的类 Coordinate。NxN 布尔数组初始化为 false 以跟踪宾果卡上划掉的内容。

N^2 次迭代宾果卡并将每个数字添加到哈希表中，使用数字作为键和新的坐标作为值。

n 时间遍历所有将被调用的数字，从哈希表中检索坐标，并更新布尔数组的状态。在调用重复数字的情况下，您必须检索和更新布尔数组，直到哈希表不包含键。

4N 时间检查布尔数组上的每个方向以进行第一次宾果游戏

N^2 + n*4N 总运行时间

于 2016-01-06T01:17:03.067 回答