在2D矩阵中找出相同的彩色块
我试图从2D矩阵的左上角开始找出一个相同颜色区域的块。 例如：我有以下矩阵：
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 ++解决方案会更好。
您忘记了瓷砖可以在所有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取决于我们是在中间，边缘还是在角落）。
我们可以使用递归来搜索相邻的区块，或者我们可以使用队列来跟踪仍然需要搜索的区块，并重复搜索队列前面的区块，直到没有剩余区块。
#include #include #include #include #include typedef std::vector vec_1d; typedef std::vector 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 position; std::queue 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
我认为在以下情况下您的代码可能有问题：
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) ，它返回作为参数传递的块旁边的块列表。
希望能帮助到你！