Finding Out Same Colored Block In A 2d Matrix

I am trying to find out a block of same colored region starting from the top left corner in a 2D matrix. For example: I have the following Matrix: 1 1 1 2 2 3 1 1 2 3 4 5 1 1 1 1 3

Solution 1:

You forgot that the tiles can touch along both axes, in all 4 directions.

Consider the following input:

1 1 1 1 1 1
2 2 2 3 3 1
1 1 1 1 3 1
1 3 3 3 3 1
1 1 1 1 1 1

I wrote a new algorithm in two versions -- one using recursion, the other a loop and queue. It is similar to what J.Mac described in his answer.

The algorithm is simple. We are given a target color to search for, the position to search at, an input matrix of colors, and output matrix of flags to identify matched tiles.

To search a tile:

• If the tile has the correct color AND it is not marked
  • Mark the tile
  • Search all neighboring tiles (2-4 depending on whether we're in the middle, at the edge or in the corner).

We can either use recursion to search the neighboring tiles, or we can use a queue to keep track of the tiles that still need to be searched and repeatedly searching tiles from the front of the queue until none remain.

#include<cstdint>#include<vector>#include<queue>#include<string>#include<iostream>typedef std::vector<int32_t> vec_1d;
typedef std::vector<vec_1d> vec_2d;

// Print the 2d vector with a labelvoiddump(std::string const& label, vec_2d const& v){
    std::cout << label << "\n";
    for (std::size_ty(0); y < v.size(); ++y) {
        for (std::size_tx(0); x < v[0].size(); ++x) {
            std::cout << v[y][x] << " ";
        }
        std::cout << "\n";
    }
    std::cout << "\n";
}

// Recursive implementation of the searchvoidfind_connected_r(int32_t target_color
    , std::size_t x
    , std::size_t y
    , vec_2d const& colors
    , vec_2d& result){
    if ((result[y][x] == 1) || (colors[y][x] != target_color)) {
        return;
    }

    result[y][x] = 1;

    std::size_twidth(colors[0].size());
    std::size_theight(colors.size());

    if (x > 0) {
        find_connected_r(target_color, x - 1, y, colors, result);
    }
    if (y > 0) {
        find_connected_r(target_color, x, y - 1, colors, result);
    }
    if (x < (width - 1)) {
        find_connected_r(target_color, x + 1, y, colors, result);
    }
    if (y < (height - 1)) {
        find_connected_r(target_color, x, y + 1, colors, result);
    }
}

// Non-recursive implementation of the searchvoidfind_connected(int32_t target_color
    , std::size_t x
    , std::size_t y
    , vec_2d const& colors
    , vec_2d& result){
    std::size_twidth(colors[0].size());
    std::size_theight(colors.size());

    typedef std::pair<std::size_t, std::size_t> position;
    std::queue<position> s;

    s.push(position(x, y));

    while (!s.empty()) {
        position pos(s.front());
        s.pop();

        if (result[pos.second][pos.first] == 1) {
            continue;
        }
        if (colors[pos.second][pos.first] != target_color) {
            continue;
        }
        result[pos.second][pos.first] = 1;

        if (pos.first > 0) {
            s.push(position(pos.first - 1, pos.second));
        }
        if (pos.second > 0) {
            s.push(position(pos.first, pos.second - 1));
        }
        if (pos.first < (width - 1)) {
            s.push(position(pos.first + 1, pos.second));
        }
        if (pos.second < (height - 1)) {
            s.push(position(pos.first, pos.second + 1));
        }
    }
}

// Entry point to the search, select the implementation with last paramvec_2d find_connected(std::size_t x, std::size_t y, vec_2d const& colors, bool recursive){
    if (colors.empty() || colors[0].empty()) {
        throw std::runtime_error("Invalid input array size");
    }

    int32_ttarget_color(colors[y][x]);

    vec_2d result(colors.size(), vec_1d(colors[0].size(), 0));

    if (recursive) {
        find_connected_r(target_color, x, y, colors, result);
    } else {
        find_connected(target_color, x, y, colors, result);
    }

    return result;
}



intmain(){
    vec_2d colors{
        { 1, 1, 1, 1, 1, 1 }
        , { 2, 2, 2, 3, 3, 1 }
        , { 1, 1, 1, 1, 3, 1 }
        , { 1, 3, 3, 3, 3, 1 }
        , { 1, 1, 1, 1, 1, 1 }
    };

    dump("Input", colors);
    dump("Search from (0,0) Recursive", find_connected(0, 0, colors, true));
    dump("Search from (0,0) Loop", find_connected(0, 0, colors, false));
    dump("Search from (1,1) Recursive", find_connected(1, 1, colors, true));
    dump("Search from (1,1) Loop", find_connected(1, 1, colors, false));
    dump("Search from (1,3) Recursive", find_connected(1, 3, colors, true));
    dump("Search from (1,3) Loop", find_connected(1, 3, colors, false));
}

Output:

Input
111111222331111131133331111111Searchfrom (0,0) Recursive111111000001111101100001111111Searchfrom (0,0) Loop
111111000001111101100001111111Searchfrom (1,1) Recursive000000111000000000000000000000Searchfrom (1,1) Loop
000000111000000000000000000000Searchfrom (1,3) Recursive000000000110000010011110000000Searchfrom (1,3) Loop
000000000110000010011110000000

---

Printing coordinates

This is very simple, like dump(...).

We iterate through all the elements, but instead of printing values we print coordinates, and only when the element value is not 0.

void dump_coordinates(std::string const& label, vec_2d const& v)
{
    std::cout << label << "\n";
    for (std::size_t y(0); y < v.size(); ++y) {
        for (std::size_t x(0); x < v[0].size(); ++x) {
            if (v[y][x]) {
                std::cout << "(" << x << ", " << y << ") ";
            }
        }
    }
    std::cout << "\n";
}

Call it:

dump_coordinates("Coordinates searching from (1,3)", find_connected(1, 3, colors, true));

And you get:

Input111111222331111131133331111111

...

Search from (1,3) Loop
000000000110000010011110000000

Coordinates searching from (1,3)
(3, 1) (4, 1) (4, 2) (1, 3) (2, 3) (3, 3) (4, 3)

NB: Coordinates are (row, column), and both are 0-indexed. The coordinates are not sorted in order of search.

---

Replacing connected elements with another color

Since we already have a method to obtain a mask of all the connected elements, we just need to use this mask to change all the appropriate values.

This is similar to what we did in dump_coordinates(...).

Again, we iterate over all the elements, but this time instead of printing, we change the color value at given position when the mask value is not 0.

Code:

vec_2d& change_masked(int32_t new_color
    , vec_2d& colors
    , vec_2d const& mask){
    for (std::size_ty(0); y < mask.size(); ++y) {
        for (std::size_tx(0); x < mask[0].size(); ++x) {
            if (mask[y][x]) {
                colors[y][x] = new_color;
            }
        }
    }

    return colors;
}

Call it:

dump("Search from (0,0), replace all found with color from (1,1)"
    , change_masked(colors[1][1], colors, find_connected(0, 0, colors, true)));

Output:

Input
111111222331111131133331111111Searchfrom (0,0) Recursive111111000001111101100001111111

...

Searchfrom (0,0), replace all found with color from (1,1)
222222222332222232233332222222

Solution 2:

I think you might have a problem with your code in the following case:

11211A111

Imagine A's color was 1. It should be stored as touching, but as the block above isn't of the same color, A will be considered as not touching.

---

My approach for this kind of algorithm would be something like the following pseudo-code (although yours seems good if the above is fixed)

/** Method to find all touching blocks of the same color */voidfindColoredNeighbors(Block block){
      // Add current block to 'touching'
      touching_array[block.x][block.y] = 1;

      // Check all adyacent blocks to see if any of them matches the colorfor (Position position: getAdyacentBlocks(block)){
          // If a block matches the color, we have to make sure it isn't stored// as touching yet to avoid infite recursionif((colors_array[position.x][position.y] == block.color) && (touching_array[position.x][position.y] != 1))
              findColoredNeighbors(getBlock(position.x, position.y));       
      }
    }

This method assumes that you clear touching_array before calling it, and you have a getAdyacentBlocks(Block b) which returns a list of the blocks next to the one passed as parameter.

Hope it helps!