0

我想为 Boggle 板生成邻接矩阵。Boggle board 是一个在 nxn 矩阵中有字母的地方，如下所示： http ://www.wordtwist.org/sample.gif

每个小区都连接到其相邻小区；基本上我们向上/向下/向左/向右/对角线移动以连接到另一个单元格。

如果将每个单元格视为图中的一个顶点，那么我们可以找到 boggle board 的邻接矩阵。

我想出了以下公式来查找相邻的单元格：假设单元格的索引从 0 开始，并且从左到右编号。i = 单元格索引，n = 行数/列数。所以在 3x3 矩阵中，i=0 将是第一个单元格，n 是 3。

up = i-n
down = i+n
left = i-1
right = i+1
diagonal 1 = i-(n+1), i+(n+1)
diagonal 2 = i-(n-1), i+(n-1)

上述公式在角落单元格的情况下失败。如何排除极端情况下的无效单元格？

4

1 回答 1

1

您不必“排除”任何内容，只需检查您的结果以查看它是否在界限内，如果不是，则没有有效的单元格。（即，如果您位于 3x3 矩阵的左上角 (i = 0)，则向上 (i - n) 为 (0 - 3 = -3)。由于 -3 在矩阵的边界之外，因此没有有效细胞。

因此，如果您正在搜索并且想要沿着“向上”相邻单元格移动，请首先检查该位置是否在边界内，如果不是，那么您就在最后。

要检查您是在矩阵的左边缘还是右边缘，请使用：

if i % (n-1) == 0// 右边缘

if i % (n) == 0// 左边缘

于 2013-02-06T22:28:57.990 回答