Finding Out Same Colored Block In A 2D Matrix
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 label
void dump(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) {
std::cout << v[y][x] << " ";
}
std::cout << "\n";
}
std::cout << "\n";
}
// Recursive implementation of the search
void find_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_t width(colors[0].size());
std::size_t height(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 search
void find_connected(int32_t target_color
, std::size_t x
, std::size_t y
, vec_2d const& colors
, vec_2d& result)
{
std::size_t width(colors[0].size());
std::size_t height(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 param
vec_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_t target_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;
}
int main()
{
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
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
Search from (0,0) Recursive
1 1 1 1 1 1
0 0 0 0 0 1
1 1 1 1 0 1
1 0 0 0 0 1
1 1 1 1 1 1
Search from (0,0) Loop
1 1 1 1 1 1
0 0 0 0 0 1
1 1 1 1 0 1
1 0 0 0 0 1
1 1 1 1 1 1
Search from (1,1) Recursive
0 0 0 0 0 0
1 1 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
Search from (1,1) Loop
0 0 0 0 0 0
1 1 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
Search from (1,3) Recursive
0 0 0 0 0 0
0 0 0 1 1 0
0 0 0 0 1 0
0 1 1 1 1 0
0 0 0 0 0 0
Search from (1,3) Loop
0 0 0 0 0 0
0 0 0 1 1 0
0 0 0 0 1 0
0 1 1 1 1 0
0 0 0 0 0 0
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:
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
...
Search from (1,3) Loop
0 0 0 0 0 0
0 0 0 1 1 0
0 0 0 0 1 0
0 1 1 1 1 0
0 0 0 0 0 0
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_t y(0); y < mask.size(); ++y) {
for (std::size_t x(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
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
Search from (0,0) Recursive
1 1 1 1 1 1
0 0 0 0 0 1
1 1 1 1 0 1
1 0 0 0 0 1
1 1 1 1 1 1
...
Search from (0,0), replace all found with color from (1,1)
2 2 2 2 2 2
2 2 2 3 3 2
2 2 2 2 3 2
2 3 3 3 3 2
2 2 2 2 2 2
Solution 2:
I think you might have a problem with your code in the following case:
1 1 2
1 1 A
1 1 1
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 */
void findColoredNeighbors(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 color
for (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 recursion
if((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!
Post a Comment for "Finding Out Same Colored Block In A 2D Matrix"