Превращение двумерного массива разного цвета в один цвет оптимально
Я пытаюсь найти решение головоломки «Flood It». Основная идея состоит в том, чтобы превратить целую N * M игровую доску из k разных цветов в один цвет. Я должен начать с верхнего левого угла доски и превратить один и тот же цветной блок в один из цветов соседних узлов и, таким образом, двигаться вперед и, наконец, залить всю доску в один цвет. Например:
Initial Board:
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
Final Board:
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
где 1,2,3,4,5 представляет разные цвета. Я подготовил код C ++ для определения площади блока такого же цвета в любой позиции на доске. Это может быть применено сначала в верхней левой ячейке, а затем в соседних узлах для заливки цвета. Мой код выглядит следующим образом:
#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);
}
}// 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;
}
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";
}
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 }
};
}
Как превратить всю плату / матрицу в один цвет, изучив соседние узлы?
Решение
В вашем коде есть куча вещей, которые я не понимаю, поэтому вместо того, чтобы пытаться их исправить, я создам новую функцию, и вы можете сравнить их.
// this function is called when the user inputs the x and y values
// the colors vector will be modified in place by reference
void change_color(int x, int y, vec_2d& colors)
{
int target_color = colors[x][y];
// call the recursive flood fill function
flood_fill(0, 0, target_color, colors);
}
//this function is the recursive flood fill
void flood_fill(int x, int y, const int target_color, vec_2d& colors)
{
// if the current tile is already the target color, do nothing
if (colors[x][y] == target_color) return;
// only need to go right and down, since starting from top left
// Also, only goes to the next tile if the next tile's color is
// the same as the current tile's color
if (x < colors.size()-1 && colors[x+1][y] == colors[x][y])
{
flood_fill(x+1, y, target_color, colors);
}
if (y < colors[0].size()-1 && colors[x][y+1] == colors[x][y])
{
flood_fill(x, y+1, target_color, colors);
}
// finally, fill in the current tile with target_color
colors[x][y] = target_color;
}
РЕДАКТИРОВАТЬ: Так как вы имели в виду, что вы хотели решить игру, а не реализовать игру …
Следите за тем, какие цвета все еще доступны на доске. На каждом «повороте» найдите цвет, который будет заполнять большую часть области плитки, начиная с верхнего левого угла. Повторяйте, пока все плитки не будут заполнены одинаковым цветом.
Это скорее метод грубой силы, и, возможно, существует более оптимизированный метод, но, на мой взгляд, это самый основной метод.
Другие решения
Возможный алгоритм верхнего уровня для решения этой загадки состоит в том, чтобы повторять следующее, пока на всей доске не будет только одного цвета:
- Найти все смежные цветовые области. Обработайте область в (0,0) как первичную, все остальные как вторичную.
- Выберите самую большую (по количеству плиток) вторичную область, цвет которой отличается от цвета основной области. Давайте назовем цвет этого вторичного региона new_color.
- Перекрасить основной регион в new_color.
Мы должны держать cumulative_mask отслеживать все плитки, которые уже определены как часть некоторого региона.
Сначала мы находим основной регион, начиная поиск с (0,0), и обновляем наш cumulative_mask с результатом.
Затем повторяйте, пока не будет найдено больше регионов:
- Найдите позицию первого нулевого фрагмента в маске cumulative_mask, у которой есть хотя бы один ненулевой фрагмент в маске первичной области.
- Найти регион, начиная с этой позиции.
- Обновите cumulative_mask с маской этого региона.
Просто выполните итерацию по вторичным регионам и найдите регион с наибольшим количеством, который имеет цвет, отличный от основного региона.
(также на coliru)
Примечание. Преднамеренно написано так, чтобы можно было понять алгоритм. Это, безусловно, может быть рефакторинг, и он пропускает много проверки ошибок.
#include <cstdint>
#include <vector>
#include <queue>
#include <string>
#include <iostream>
typedef std::vector<int32_t> vec_1d;
typedef std::vector<vec_1d> vec_2d;
typedef std::pair<std::size_t, std::size_t> position;
position const INVALID_POSITION(-1, -1);
int32_t const INVALID_COLOR(0);
// ============================================================================
struct region_info
{
int32_t color;
vec_2d mask;
std::size_t count() const
{
std::size_t result(0);
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]) {
++result;
}
}
}
return result;
}
};
struct region_set
{
// The region that contains (0, 0)
region_info primary;
// All other regions
std::vector<region_info> secondary;
};
// ============================================================================
// 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";
}
// Print the coordinates of non-zero elements of 2D vector with a label
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";
}
void dump(region_info const& ri)
{
std::cout << "Region color: " << ri.color << "\n";
std::cout << "Region count: " << ri.count() << "\n";
dump("Region mask:", ri.mask);
}
void dump(region_set const& rs)
{
std::cout << "Primary Region\n" << "\n";
dump(rs.primary);
for (std::size_t i(0); i < rs.secondary.size(); ++i) {
std::cout << "Secondary Region #" << i << "\n";
dump(rs.secondary[i]);
}
}
// ============================================================================
// Find connected tiles - implementation
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());
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));
}
}
}
// Find connected tiles - convenience wrapper
vec_2d find_connected(std::size_t x, std::size_t y, vec_2d const& colors)
{
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));
find_connected(target_color, x, y, colors, result);
return result;
}
// ============================================================================
// Change color of elements at positions with non-zero mask value to new color
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;
}
// Combine two masks
vec_2d combine(vec_2d const& v1, vec_2d const& v2)
{
vec_2d result(v1);
for (std::size_t y(0); y < v2.size(); ++y) {
for (std::size_t x(0); x < v2[0].size(); ++x) {
if (v2[y][x]) {
result[y][x] = v2[y][x];
}
}
}
return result;
}
// Find position of first zero element in mask
position find_first_zero(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]) {
return position(x, y);
}
}
}
return INVALID_POSITION;
}
bool has_nonzero_neighbor(std::size_t x, std::size_t y, vec_2d const& mask)
{
bool result(false);
if (x > 0) {
result |= (mask[y][x - 1] != 0);
}
if (y > 0) {
result |= (mask[y - 1][x] != 0);
}
if (x < (mask[0].size() - 1)) {
result |= (mask[y][x + 1] != 0);
}
if (y < (mask.size() - 1)) {
result |= (mask[y + 1][x] != 0);
}
return result;
}
// Find position of first zero element in mask
// which neighbors at least one non-zero element in primary mask
position find_first_zero_neighbor(vec_2d const& mask, vec_2d const& primary_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]) {
if (has_nonzero_neighbor(x, y, primary_mask)) {
return position(x, y);
}
}
}
}
return INVALID_POSITION;
}
// ============================================================================
// Find all contiguous color regions in the image
// The region starting at (0,0) is considered the primary region
// All other regions are secondary
// If parameter 'only_neighbors' is true, search only for regions
// adjacent to primary region, otherwise search the entire board
region_set find_all_regions(vec_2d const& colors, bool only_neighbors = false)
{
region_set result;
result.primary.color = colors[0][0];
result.primary.mask = find_connected(0, 0, colors);
vec_2d cumulative_mask = result.primary.mask;
for (;;) {
position pos;
if (only_neighbors) {
pos = find_first_zero_neighbor(cumulative_mask, result.primary.mask);
} else {
pos = find_first_zero(cumulative_mask);
}
if (pos == INVALID_POSITION) {
break; // No unsearched tiles left
}
region_info reg;
reg.color = colors[pos.second][pos.first];
reg.mask = find_connected(pos.first, pos.second, colors);
cumulative_mask = combine(cumulative_mask, reg.mask);
result.secondary.push_back(reg);
}
return result;
}
// ============================================================================
// Select the color to recolor the primary region with
// based on the color of the largest secondary region of non-primary color
int32_t select_color(region_set const& rs)
{
int32_t selected_color(INVALID_COLOR);
std::size_t selected_count(0);
for (auto const& ri : rs.secondary) {
if (ri.color != rs.primary.color) {
if (ri.count() > selected_count) {
selected_count = ri.count();
selected_color = ri.color;
}
}
}
return selected_color;
}
// ============================================================================
// Solve the puzzle
// If parameter 'only_neighbors' is true, search only for regions
// adjacent to primary region, otherwise search the entire board
// Returns the list of selected colors representing the solution steps
vec_1d solve(vec_2d colors, bool only_neighbors = false)
{
vec_1d selected_colors;
for (int32_t i(0);; ++i) {
std::cout << "Step #" << i << "\n";
dump("Game board: ", colors);
region_set rs(find_all_regions(colors, true));
dump(rs);
int32_t new_color(select_color(rs));
if (new_color == INVALID_COLOR) {
break;
}
std::cout << "Selected color: " << new_color << "\n";
selected_colors.push_back(new_color);
change_masked(new_color, colors, rs.primary.mask);
std::cout << "\n------------------------------------\n\n";
}
return selected_colors;
}
// ============================================================================
int main()
{
vec_2d colors{
{ 1, 1, 1, 1, 1, 1 }
, { 2, 2, 2, 3, 3, 1 }
, { 1, 1, 4, 5, 3, 1 }
, { 1, 3, 3, 4, 3, 1 }
, { 1, 1, 1, 1, 1, 1 }
};
vec_1d steps(solve(colors, true));
std::cout << "Solved in " << steps.size() << " step(s):\n";
for (auto step : steps) {
std::cout << step << " ";
}
std::cout << "\n\n";
}
// ============================================================================
Вывод программы:
Step #0
Game board:
1 1 1 1 1 1
2 2 2 3 3 1
1 1 4 5 3 1
1 3 3 4 3 1
1 1 1 1 1 1
Primary Region
Region color: 1
Region count: 18
Region mask:
1 1 1 1 1 1
0 0 0 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1
Secondary Region #0
Region color: 2
Region count: 3
Region mask:
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
Secondary Region #1
Region color: 3
Region count: 4
Region mask:
0 0 0 0 0 0
0 0 0 1 1 0
0 0 0 0 1 0
0 0 0 0 1 0
0 0 0 0 0 0
Secondary Region #2
Region color: 4
Region count: 1
Region mask:
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
Secondary Region #3
Region color: 3
Region count: 2
Region mask:
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 1 1 0 0 0
0 0 0 0 0 0
Secondary Region #4
Region color: 4
Region count: 1
Region mask:
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 1 0 0
0 0 0 0 0 0
Selected color: 3
------------------------------------
Step #1
Game board:
3 3 3 3 3 3
2 2 2 3 3 3
3 3 4 5 3 3
3 3 3 4 3 3
3 3 3 3 3 3
Primary Region
Region color: 3
Region count: 24
Region mask:
1 1 1 1 1 1
0 0 0 1 1 1
1 1 0 0 1 1
1 1 1 0 1 1
1 1 1 1 1 1
Secondary Region #0
Region color: 2
Region count: 3
Region mask:
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
Secondary Region #1
Region color: 4
Region count: 1
Region mask:
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
Secondary Region #2
Region color: 5
Region count: 1
Region mask:
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0
Secondary Region #3
Region color: 4
Region count: 1
Region mask:
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 1 0 0
0 0 0 0 0 0
Selected color: 2
------------------------------------
Step #2
Game board:
2 2 2 2 2 2
2 2 2 2 2 2
2 2 4 5 2 2
2 2 2 4 2 2
2 2 2 2 2 2
Primary Region
Region color: 2
Region count: 27
Region mask:
1 1 1 1 1 1
1 1 1 1 1 1
1 1 0 0 1 1
1 1 1 0 1 1
1 1 1 1 1 1
Secondary Region #0
Region color: 4
Region count: 1
Region mask:
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
Secondary Region #1
Region color: 5
Region count: 1
Region mask:
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0
Secondary Region #2
Region color: 4
Region count: 1
Region mask:
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 1 0 0
0 0 0 0 0 0
Selected color: 4
------------------------------------
Step #3
Game board:
4 4 4 4 4 4
4 4 4 4 4 4
4 4 4 5 4 4
4 4 4 4 4 4
4 4 4 4 4 4
Primary Region
Region color: 4
Region count: 29
Region mask:
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 0 1 1
1 1 1 1 1 1
1 1 1 1 1 1
Secondary Region #0
Region color: 5
Region count: 1
Region mask:
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0
Selected color: 5
------------------------------------
Step #4
Game board:
5 5 5 5 5 5
5 5 5 5 5 5
5 5 5 5 5 5
5 5 5 5 5 5
5 5 5 5 5 5
Primary Region
Region color: 5
Region count: 30
Region mask:
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
Solved in 4 step(s):
3 2 4 5