Flood fill with bitwise operations

Question

I have a bit map stored as a (fixed) number of unsigned integers, e.g:

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

...is stored as the integer array [ 9, 10, 13, 6 ] (top-down, most significant bit on the left).

I would like to implement a flood-fill algorithm. For instance, if m is the map depicted above, floodFill(m, 3, 2) should produce the map:

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

(Here, 3,2 corresponds to third row (0-indexed), second column (from the right). The answer would be encoded as [ 8, 8, 12, 6 ].)

I can certainly implement one of the standard approaches, but I wonder whether I can do better using bit manipulation tricks.

For instance, if part of the solution is contained in a map m0, I think I m0 | ((m0 >> 1) & m) "grows" the flood fill to the right.

Is this a standard trick to parallelize flood fill on bit maps? Can anyone come up with a complete algorithm? Prove interesting bounds on running time?

Edit: some additional examples:

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

Following works:

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;
}

Test it: (I use C++11 here)

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;
}