2

让我们考虑一个双向数组，声明如下：

#include <stdbool.h>

bool array[N1][N2];

我必须知道这个数组的每一行是否true在同一位置都有一个值。

例如以下是可以的：

{ 
  { 1, 0, 1, 0 },
  { 1, 0, 0, 1 },
  { 0, 0, 1, 1 }
}

而这是不正确的：

{ 
  { 1, 0, 1, 0 },
  { 1, 0, 1, 0 },
  { 0, 0, 1, 1 }
}

我试过这个：

static uintmax_t hash(const bool *t, size_t n) 
{
    uintmax_t retv = 0U;
    for (size_t i = 0; i < n; ++i)
        if (t[i] == true)
            retv |= 1 << i;
    return retv;
}

static int is_valid(bool n) 
{ 
    return n != 0 && (n & (n - 1)) == 0;
}

bool check(bool t[N1][N2])
{
    uintmax_t thash[N1];

    for (size_t i = 0; i < N1; ++i)
        thash[i] = hash(t[i], N2);

    for (size_t i = 0; i < N1; ++i)
        for (size_t j = 0; j < N1; ++j)
            if (i != j && !is_valid(thash[i] & thash[j]))
                return 0;

    return 1;
}

但它仅适用于N1 <= sizeof(uintmax_t) * CHAR_BIT. 你知道解决它的最佳方法吗？

4

2 回答 2

1

不要将位打包成整数。相反，遍历每两条相邻的行i并i+1求和!(a[i][j] ^ a[i+1][j])（两行中位的 XOR 的非）。每行的总和必须恰好为 1。

注意我使用的是逻辑not而不是按位not。我不想得到-1s（这是按位不为0）。

于 2012-11-01T19:16:12.227 回答
1

为什么不创建另一个大小为 N2 （列数）的数组，将其设置为 all true，然后and每行中的每一列都使用它。最后，检查您的新数组是否正好有一个设置位。

bool array[N1][N2];  // this is initialized somehow
bool result[N2];
int i, j;

// initialize result array
for (j = 0; j < N2; ++j)
{
    result[j] = 1;
}

// Now go through the array, computing the result
for (i = 0; i < N1; ++i)
{
    for (j = 0; j < N2; ++j)
    {
        result[j] &= array[i][j];
    }
}

// At this point, you can check the result array.
// If your array is valid, then result should have only one '1' in it.
于 2012-11-01T19:22:45.623 回答