在二维矩阵中找出相同颜色的块

Finding out same colored block in a 2D matrix

我试图从二维矩阵的左上角开始找出一块相同颜色的区域。例如:我有以下矩阵:

1 1 1 2 2 3
1 1 2 3 4 5
1 1 1 1 3 4
1 4 3 2 1 5
2 3 4 5 1 2

比如说,初始左上角是1,我想找出相邻的包含1的区域(我只会考虑从左上角开始)。在上面的矩阵中,数字 1、2、3、4、5 代表不同的颜色。我尝试使用以下代码段找出相同颜色的块:

colors = ["red", "green", "blue", "purple", "orange"]

# create an array of the colors so we can do work on it
colors_array = [[random.randint(0, len(colors)-1) for x in range(num_wide)] for x in range(num_high)]

// keep track of what colors are touching in a giant array
touching_array = [[[0 for x in range(num_col)] for x in range(num_row)] for x in range(len(colors))]
origin_color = colors_array[0][0]
for x in range(num_row):
for y in range(num_col):
    # first row only cares about what's to the left of it
    if (x == 0):
        # if this is the same color as the origin
        if colors_array[x][y] == origin_color:
            # store a '1' signifying that this color is touching
            touching_array[origin_color][x][y] = 1
        else:
            # once they don't match, stop looking
            break
    # other rows need to match the row above it
    else:
        # if this color is the same color as the origin
        if (colors_array[x][y] == origin_color):
            # AND the one above it is "touching"
            if (colors_array[x][y] == touching_array[origin_color][x-1][y]):
                # store a '1' signifying that this color is touching
                touching_array[origin_color][x][y] = 1

但是我没有得到与输出从左上角开始的相同颜色的块。上面的代码段有什么问题吗?我将如何使其正确?如果有人提供上述问题的 C/C++ 解决方案会更好。

我认为在以下情况下您的代码可能有问题:

 1 1 2
 1 1 A
 1 1 1

假设A的颜色为1。它应该存储为接触,但由于上面的块不是相同的颜色,A将被视为不接触。


我对这种算法的方法类似于下面的伪代码(尽管如果上面的问题得到解决,你的看起来不错)

  /** 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));       
      }
    }

此方法假定您在调用它之前清除了 touching_array,并且您有一个 getAdyacentBlocks(Block b) 其中 returns 作为参数传递的块旁边的块列表。

希望对您有所帮助!

您忘记了瓷砖可以沿两个轴在所有 4 个方向上接触。

考虑以下输入:

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

我写了两个版本的新算法——一个使用递归,另一个使用循环和队列。这与 J.Mac 在他的回答中描述的相似。

算法简单。我们有一个要搜索的目标颜色,要搜索的位置,一个输入颜色矩阵,并输出 标志矩阵 以识别匹配的图块。

要搜索图块:

  • 如果图块颜色正确且未标记
    • 标记瓷砖
    • 搜索所有相邻的图块(2-4 取决于我们是在中间、边缘还是角落)。

我们可以使用递归来搜索相邻的图块,也可以使用队列来跟踪仍需要搜索的图块,并从队列的前面重复搜索图块,直到 none留下来。

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

输出:

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

打印坐标

这个很简单,喜欢dump(...)

我们遍历所有元素,但不是打印值,而是打印坐标,并且仅当元素值不为 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";
}

称之为:

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

你得到:

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)

注意:坐标是(行,列),并且都是从 0 开始索引的。坐标按搜索顺序排序。


用另一种颜色替换连接的元素

由于我们已经有了获取所有连通元素掩码的方法,我们只需要使用这个掩码来更改所有适当的值。

这与我们在 dump_coordinates(...) 中所做的类似。

同样,我们遍历所有元素,但这次不是打印,而是在掩码值不为 0 时更改给定位置的颜色值。

代码:

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

称之为:

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

输出:

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