0

我正在尝试阅读约束满足问题并尝试对其进行编码以解决一些示例问题。我遇到了http://rosettacode.org/wiki/Zebra_puzzle#C.2B.2B来解决经典的斑马难题。在rosetta code website给出的C代码中，有以下功能。我只给出了几行。我不知道这两个if语句的目的是什么以及它们是如何工作的。有人可以解释一下吗？

int checkHouses(int ha[5][5])
{
...
    int c_add = 0, c_or = 0;
    int m_add = 0, m_or = 0;
    int d_add = 0, d_or = 0;
    int a_add = 0, a_or = 0;
    int s_add = 0, s_or = 0;

    for (int i = 0; i < 5; i++) {
        // Uniqueness tests.
        if (ha[i][C] >= 0) {
            c_add += (1 << ha[i][C]);
            c_or |= (1 << ha[i][C]);
        }
        if (ha[i][M] >= 0) {
            m_add += (1 << ha[i][M]);
            m_or |= (1 << ha[i][M]);
        }
        if (ha[i][D] >= 0) {
            d_add += (1 << ha[i][D]);
            d_or |= (1 << ha[i][D]);
        }
        if (ha[i][A] >= 0) {
            a_add += (1 << ha[i][A]);
            a_or |= (1 << ha[i][A]);
        }
        if (ha[i][S] >= 0) {
            s_add += (1 << ha[i][S]);
            s_or |= (1 << ha[i][S]);
        }
    }

    if ((c_add != c_or) || (m_add != m_or) || (d_add != d_or)
        || (a_add != a_or) || (s_add != s_or)) {
        return Invalid;
    }

    if ((c_add != 0b11111) || (m_add != 0b11111) || (d_add != 0b11111)
        || (a_add != 0b11111) || (s_add != 0b11111)) {

        return Underfull;
}
4

1 回答 1

1

ha[0..4][评论实际上解释了它：他们正在验证x]的每个值在 x之间没有重复值。

至于它是如何做到的：每个值都分配有一个位位置，这样1<<ha[i][x]将产生一个数字，其中只有该位置集中的位。x_or将是这些值的 OR，而 x_add是它们的总和。如果存在重复值，则不会对 x 产生影响_or（该位已设置），但会对x产生影响_add；因此，它们会有所不同。

于 2015-10-19T16:16:43.547 回答