C语言 计算网格上连通组的相邻空点的有效方法

Question

一个连通的组是指在一个网格上一组相等的顶点在水平或垂直方向上相邻。

例如，在此网格中，.为空点，则有4个连通的组

X O O .      X       O O
. X O X  ->       X    O  X
X X O X         X X    O  X

您还可以看到每组有1个连接的空点。

我正在尝试计算这些连通的空点的数量，给定一个网格和指向一个顶点的坐标。

如果输入是，

. . X X X O O . 
X X . X . X O X 
. X X X X X O X 
X X . O O X . X 
(0, 2)

输出应该是7，因为包含(0, 2)(行，列)顶点的大群有7个连接的空点。

如果你熟悉围棋(baduk)，连接空点也就是自由。这个操作是在围棋中分析一个位置的例程的核心，它必须快速完成。

下面是我的尝试。它在很多方面都非常低效，涉及很多分支和递归。我正在跟踪4个可能的方向，并在有空白空间时增加计数，并在计数已完成的顶点上标记不计数两次。

你能告诉我如何有效地解决这个问题吗?

一般算法改进和x86- avx2特定的优化都是受欢迎的。

typedef __attribute__((vector_size(32))) char vec8_c;
enum {H = 4, W = 8};
static int count_();
static int count__();
static int count(vec8_c x, int i, int j) {
vec8_c m = {0};
return count_((char *)&x, (char *)&m, i, j, i * W + j);
}
static int count_(char *x, char *m, int i, int j, int idx) {
m[idx] = 1;
int r = 0;
if (j - 1 >= 0) {
r += count__(x, m, i, j - 1, idx - 1, idx);
}
if (j + 1 < W) {
r += count__(x, m, i, j + 1, idx + 1, idx);
}
if (i - 1 >= 0) {
r += count__(x, m, i - 1, j, idx - W, idx);
}
if (i + 1 < H) {
r += count__(x, m, i + 1, j, idx + W, idx);
}
return r;
}
static int count__(char *x, char *m, int i, int j, int idx, int idx_) {
if (!m[idx]) {
if (!x[idx]) {
m[idx] = 1;
return 1;
} else if (x[idx] == x[idx_]) {
return count_(x, m, i, j, idx);
}
}
return 0;
}

在线运行。

Answer 1

根据描述，我将把问题转化为交/并;

• 从连接的组件创建掩码C
• 从空像素创建一个蒙版E
• 通过连接C的移位版本来创建一个更大的掩码MM = C<<1 | C^^1 | C >> 1 | C^^-1
• 返回PopCount(M &E)

这种方法应该很容易向量化，甚至是自动向量化。

当C足够大时，使用SIMD寄存器在16x8的块中工作，其中每个位表示掩码中的布尔值。然后可以使用_mm_slli_epi16/_mm_srli_epi16或AVX2/-512中的等价物通过alignr/左/右移动整个块，不幸的是，跨银行移动有点昂贵。

对于特定输入:

. . X X X O O . -> C = 0 0 1 1 1 0 0 0  E = 1 1 0 0 0 0 0 1
X X . X . X O X        1 1 0 1 0 1 0 0      0 0 1 0 1 0 0 0
. X X X X X O X        0 1 1 1 1 1 0 0      1 0 0 0 0 0 0 0
X X . O O X . X        1 1 0 0 0 1 0 0      0 0 1 0 0 0 1 0

那么掩码M就是C向左，向右，向上，向下移动的并集

M =   0  0  0  1  1  1  0  0  0  0
0 |1  1  1  1  1  1  0  0| 0  <-- you only need the
1 |1  1  1  1  1  1  1  0| 0      inner / 'valid' area
0 |1  1  1  1  1  1  1  0| 0
1 |1  1  1  1  1  1  1  0| 0
0  1  1  0  0  0  1  0  0  0
M.*E =    1   1   0   0   0   0   0   0
0   0   1   0   1   0   0   0
1   0   0   0   0   0   0   0
0   0   1   0   0   0   1   0,  sum == 7