在2D矩阵中找出相同颜色的块 [英] Finding out same colored block in a 2D matrix

查看：70 发布时间：2020/5/7 19:30:55 python c matrix puzzle

本文介绍了在2D矩阵中找出相同颜色的块的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我正在尝试从2D矩阵的左上角开始查找相同颜色区域的块.例如:我有以下矩阵:

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 4
1 4 3 2 1 5
2 3 4 5 1 2

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

say, The initial top left corner is 1 and I want to find out the adjacent area containing 1's (I will only consider starting from the top left corner). In the above matrix the digits 1,2,3,4,5 represent different colors. I have tried using the following code segment for finding out the same colored block:

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 ++解决方案会更好.

But I haven't got the same colored block starting from top left corner as output. Is there anything wrong in the above code segment? How will I make it correct? It would be better If someone provide a C/C++ solution of the above problem.

推荐答案

您忘记了图块可以沿两个轴在所有4个方向上触摸.

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

请考虑以下输入:

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 在他的回答中描述的内容.

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.

要搜索图块:

如果图块的颜色正确且未标记

标记图块
搜索所有相邻的图块(2-4取决于我们是在中间，在边缘还是在拐角处).

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

输出:

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(...).

Printing coordinates

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

我们遍历所有元素，但是仅当元素值不为0时，才打印坐标，而不是打印坐标.

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

调用:

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)

NB:坐标为(行，列)，并且都为0索引.坐标未按搜索顺序未排序.

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

由于我们已经有了一种获取所有连接元素的掩码的方法，因此我们只需要使用此掩码来更改所有适当的值即可.

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.

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

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

同样，我们遍历所有元素，但是这次，而不是打印时，当遮罩值不为0时，我们在给定位置更改颜色值.

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.

代码:

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

这篇关于在2D矩阵中找出相同颜色的块的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文

在2D矩阵中找出相同颜色的块 [英] Finding out same colored block in a 2D matrix

问题描述

推荐答案

打印坐标

Printing coordinates

相关文章

Python最新文章

热门教程

热门工具

登录关闭

在2D矩阵中找出相同颜色的块 [英] Finding out same colored block in a 2D matrix

问题描述

推荐答案

打印坐标

Printing coordinates

相关文章

Python最新文章

热门教程

热门工具

登录 关闭

登录关闭