Herausfinden des gleichen farbigen Blocks in einer 2D-Matrix

Question

Ich versuche, einen Block von gleichfarbigen Bereich beginnend von der oberen linken Ecke in einer 2D-Matrix zu finden. Zum Beispiel: Ich habe die folgende 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 

sagen: Die anfängliche linke obere Ecke ist 1, und ich möchte mit dem angrenzenden Gebiet, um herauszufinden, 1'en (Ich werde nur betrachten von der linken oberen Ecke beginnend). In der obigen Matrix repräsentieren die Ziffern 1,2,3,4,5 verschiedene Farben. Ich habe versucht, das folgende Code-Segment unter Verwendung für die Suche nach dem gleichen farbigen Block heraus:

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 

Aber ich habe nicht den gleichen farbigen Block beginnend von oben links als Ausgang bekomme. Gibt es etwas falsches im obigen Code-Segment? Wie werde ich es richtig machen? Es wäre besser, wenn jemand eine C/C++ Lösung des obigen Problems zur Verfügung stellen würde.

Answer 1

Sie haben vergessen, dass sich die Kacheln entlang beider Achsen in allen 4 Richtungen berühren können.

Betrachten Sie die folgende Eingabe:

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 

Ich schrieb einen neuen Algorithmus in zwei Versionen - eine Rekursion, das andere eine Schleife und Warteschlange. Es ist ähnlich wie in seiner Antwort J.Mac beschrieben.

Der Algorithmus ist einfach. Wir werden eine Zielfarbe gegeben zu suchen, die Position an zu suchen, eine Eingabe Matrix von Farben und Ausgabe Matrix von Fahnen zu abgestimmt Fliesen zu identifizieren.

eine Kachel suchen:

• Wenn die Fliese die richtige Farbe hat und es
  • Mark nicht markiert ist die Fliese
  • alle benachbarten Fliesen Suchen (2-4 je nachdem, ob wir sind in der Mitte, am Rand oder in der Ecke.

Wir können entweder Rekursion die benachbarten Fliesen suchen, oder wir können eine Warteschlange verwenden Spur der Fliesen zu halten, die immer noch gesucht werden müssen und immer wieder Fliesen von der Vorderseite der Warteschlange, bis keine Suche bleiben übrig.

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

Ausgang:

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 

---

Druckkoordinaten

Dies ist sehr einfach, wie dump(...).

Wir durchlaufen alle Elemente, sondern von Druckwerten wir Koordinaten drucken, und nur dann, wenn der Wert des Elements ist nicht 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"; 
} 

es Aufruf:

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

Und Sie erhalten :

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) 

Hinweis: Koordinaten sind (Zeile, Spalte), und beide sind 0-indiziert. Die Koordinaten sind nicht in der Reihenfolge der Suche sortiert.

---

Ersetzen verbundene Elemente mit einer anderen Farbe

Da wir bereits ein Verfahren eine Maske aller angeschlossenen Elemente zu erhalten, brauchen wir nur diese Maske verwenden, um alle entsprechenden Werte zu ändern.

Dies ist ähnlich wie in dump_coordinates(...).

Wieder iterieren wir über alle Elemente, aber diesmal statt Druck, ändern wir den Farbwert an einer bestimmten Position, wenn der Maskenwert nicht 0

-Code ist:

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

Anruf es:

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

Ausgang:

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 

Answer 2

Ich denke, man könnte ein Problem mit dem Code im folgenden Fall haben:

1 1 2 
1 1 A 
1 1 1 

Stellen Sie sich eine Farbe des 1. war Es sollte als rührend gespeichert werden, sondern als der Block oben ist nicht von der gleichen Farbe, A wird als nicht berührend angesehen.

---

Mein Ansatz für diese Art von Algorithmus würde etwas wie das folgende Pseudo-Code (obwohl Ihnen gut scheint, wenn die oben festgelegt ist)

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

Diese Methode setzt voraus, dass Sie klare touching_array vor dem Aufruf es, und Sie haben eine getAdyacentBlocks(Block b), die eine Liste der Blöcke neben dem als Parameter übergebenen zurückgibt.

Hoffe es hilft!