网格上连通群相邻空点计数的有效方法

Question

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

例如，在这个网格中，.是一个空点，其中有4个连接组。

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

您还可以看到每个组都有一个连通的空点。

我试图计数这些连通的空点的数目，给定一个网格，以及指向一个组的顶点的坐标。

如果输入是，

. . 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)的游戏，那么连接空点就意味着自由。这一操作是分析围棋中某一位置的常规操作的核心，它必须快速完成。

下面是我的尝试。它在很多方面效率很低，涉及很多分支和递归。我正在跟踪四个可能的方向，并在有一个空空间的情况下递增计数，并在进行计数的顶点上加上一个标记，使其不进行两次计数。

你能说明一下如何有效地解决这个问题吗？

通用算法改进和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 M = C<<1 | C^^1 | C >> 1 | C^^-1来制作更大的掩码M
• 返回PopCount(M & E)

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

当C足够大时，使用SIMD寄存器在16x8块中工作，其中每个位表示掩码中的一个布尔值。然后，人们可以用alignr / left/right或AVX2 2/-512中的等价物上下移动整个街区，不幸的是，跨银行移动的代价有点高。

关于具体投入：

. . 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