c++ - 使用按位运算进行洪水填充

Question

我将位图存储为(固定)数量的无符号整数，例如:

1 0 0 1
1 0 1 0
1 1 0 1
0 1 1 0

...存储为整数数组[ 9, 10, 13, 6 ](自上而下，左侧最高有效位)。

我想实现一个泛洪算法。例如，如果 m 是上面描述的 map ，floodFill(m, 3, 2) 应该生成 map :

1 0 0 0
1 0 0 0
1 1 0 0
0 1 1 0

(此处，3,2 对应于第三行(索引为 0)第二列(从右起)。答案将被编码为 [ 8, 8, 12, 6 ].)

我当然可以实现其中一种标准方法，但我想知道我是否可以使用位操作技巧做得更好。

例如，如果部分解决方案包含在 map m0 中，我想我 m0 | ((m0 >> 1) & m) 向右“增长”洪水填充。

这是在位图上并行化填充的标准技巧吗？谁能想出一个完整的算法？证明有趣的运行时间界限？

编辑:一些额外的例子:

floodFill ( 0 0 1 1     , 1, 1 ) =  0 0 1 1   
            1 1 1 0                 1 1 1 0
            0 0 1 1                 0 0 1 1
            1 1 0 1                 0 0 0 1

floodFill ( 1 0 0 1     , 1, 2 ) =  0 0 0 0   
            0 1 0 0                 0 1 0 0
            0 1 0 1                 0 1 0 0
            0 0 1 1                 0 0 0 0

Answer 1

以下作品:

std::vector<unsigned> floodFill(const std::vector<unsigned>& map, unsigned int row, unsigned int column)
{
    std::vector<unsigned> res(map.size() + 2); // Add 'border' to avoid special case

    res[1 + row] = (1u << column) & map[row]; // Seed point (column: right to left)

    std::vector<unsigned> last;
    do {
        last = res;

        for (std::size_t i = 0, size = map.size(); i != size; ++i) {
            res[i + 1] |= (res[i] | res[i + 2] | (res[i + 1] << 1u) | (res[i + 1] >> 1u)) & map[i];
        }
    } while (last != res);
    res.pop_back();         // remove extra border.
    res.erase(res.begin()); // remove extra border.
    return res;
}

测试一下:(我这里用的是C++11)

int main(int argc, char *argv[])
{
    const std::vector<unsigned int> v = {9, 10, 13, 6};
    const std::vector<unsigned int> expected = {8, 8, 12, 6};
    std::vector<unsigned int> res = floodFill(v, 3, 2);

    assert(res == expected);
    assert(floodFill({3, 14, 3, 13}, 1, 1) == std::vector<unsigned int>({3, 14, 3, 1}));
    assert(floodFill({9, 4, 5, 3}, 1, 2) == std::vector<unsigned int>({0, 4, 4, 0}));
    return 0;
}