2

我正在研究一个搜索算法项目，寻找 16 谜题的解决方案。

我有两个包含二维数组的结构列表board[N][N]

列表中的数字在 0-15 范围内是唯一的，不同的是它们的顺序。

BoardA = 0  1  2  3           BoardB = 4  1  2  3  
         4  5  6  7                    0  5  6  7
         8  9 10 11                    8  9 10 11
        12 13 14 15                   12 13 14 15

如您所见，板之间的唯一区别是数字的顺序。显然，可以遍历每个板检查是否

BoardA[i][j] == BoardB[i][j]

但是，如果列表中有成百上千个板，则不希望以这种方式比较它们。

有没有办法快速或有效地比较两块板的相同性？

4

2 回答 2

1

二维数组的元素位于连续的内存块中。所以要比较两个数组，你只是比较两个内存块。最快的方法是使用memcmp(). 您没有指定每个数组元素的类型，所以我将使用int它，如果您的元素不是ints，您可以将其替换为另一种类型。

if (memcmp(BoardA, BoardB, sizeof(int) * N * N) == 0) {
  /* equal */
} else {
  not /* equal */
}
于 2017-10-30T21:50:33.423 回答
0

您可能会使用类似的技巧节省一些周期memcmp()，但实际上简单、直接的比较会优化得很好。如果您在失败时提前退出，那么它只会在数组相等的情况下比较所有元素，在这种情况下，无论如何都需要进行每次比较，即使使用memcmp().

所以保持简单：

int equals(int (*a)[4], int (*b)[4]) {
    for (int i = 0; i < 4; i += 1) {
        for (int j = 0; i < 4; j += 1) {
            if (a[i][j] != b[i][j]) return 0;
        }
    }
    return 1;
}
于 2017-10-30T21:56:42.783 回答