在二维矩阵中找出相同颜色的块
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
我试图从二维矩阵的左上角开始找出一块相同颜色的区域。例如：我有以下矩阵：
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