Come trovare efficacemente le aree nell'array bidimensionale?

Question

Ho bisogno di un'idea su come trovare efficacemente le aree sottostanti contrassegnate con 0 nella matrice bidimensionale. Va notato che ci sono altre aree, come questa immagine mostra uno dei due che possiede coordinate (0.0) e l'altra possiede coordinate (21.3).

00000000000111110000111 
00000000001111110000111 
00000000011111100000111 
00000000000111000001101 
00000000011100000011101 
00000001111100001111001 
00000111111111011111001 
00000001111100001111001 
00000000010000000011001 
00000000000000000001111 

Naturalmente un array reale sarà molto più grande. Versione ricorsiva che va da tutti i lati e si ferma al punto 1 o lato dell'array non è abbastanza veloce.

Answer 1

Sembra che tu stia cercando uno flood-fill algorithm. La pagina di wikipedia che ho linkato elenca alcuni algoritmi che potrebbero essere più veloci rispetto all'ovvio metodo ricorsivo.

Riempimento di riempimento sarà una buona corrispondenza se le aree che stai cercando sono piccole rispetto all'intero array, e non è necessario cercare tutte di di esse. Se è necessario conoscere la maggior parte o tutti, quindi calcolarli tutti in un'unica operazione utilizzando un algoritmo connected component labeling basato su unione unione può essere una scelta migliore. Ecco alcuni codice che implementa un algoritmo (nota che ho alterato per l'esecuzione in un unico passaggio):

#include <cstdio> 
#include <cstdlib> 
#include <cstring> 
#include <vector> 
#include <map> 

const char *data[] = { 
"00000000000111110000111", 
"00000000001111110000111", 
"00000000011111100000111", 
"00000000000111000001101", 
"00000000011100000011101", 
"00000001111100001111001", 
"00000111111111111111001", 
"00000001111100001111001", 
"00000000010000000011001", 
"00000000000000000001111", 
NULL 
}; 

struct label { 
private: 
    int index; 
    int rank; 
    label *parent; 
public: 
    label() 
     : index(-1), rank(0), parent(this) 
    { } 

    int getIndex(int &maxIndex) { 
     if (parent != this) 
      return find()->getIndex(maxIndex); 

     if (index < 0) 
      index = maxIndex++; 
     return index; 
    } 

    label *find() { 
     if (parent == this) 
      return this; 

     parent = parent->find(); 
     return parent; 
    } 

    label *merge(label *other) 
    { 
     label *xRoot = find(); 
     label *yRoot = other->find(); 

     if (xRoot == yRoot) 
      return xRoot; 

     if (xRoot->rank > yRoot->rank) { 
      yRoot->parent = xRoot; 
      return xRoot; 
     } else { 
      xRoot->parent = yRoot; 
      if (xRoot->rank == yRoot->rank) 
       yRoot->rank++; 
      return yRoot; 
     } 
    } 
}; 

int width, height; 

int main() { 
    for (int i = 0; data[0][i]; i++) 
     width = i + 1; 
    for (int i = 0; data[i]; i++) { 
     height = i + 1; 
    } 

    std::vector<std::vector<unsigned short> > lblinfo; 
    lblinfo.resize(height, std::vector<unsigned short>(width, 0)); 

    std::vector<label *> labels; 
    labels.push_back(NULL); // 0 is used as an unassigned flag 

    for (int y = 0; y < height; y++) { 
     for (int x = 0; x < width; x++) { 
      if (data[y][x] == '1') 
       continue; 

      // Try to find a neighboring label 
      unsigned short lblid = 0; 
      if (x != 0 && lblinfo[y][x-1] != 0) 
       lblid = lblinfo[y][x-1]; 

      // merge with cells above 
      if (y != 0) { 
       for (int x2 = x - 1; x2 <= x + 1; x2++) { 
        if (x2 < 0) 
         continue; 
        if (x2 >= width) 
         continue; 

        unsigned short otherid = lblinfo[y - 1][x2]; 
        if (!otherid) 
         continue; 

        if (!lblid) 
         lblid = otherid; 
        else { 
         labels[lblid]->merge(labels[otherid]); 
        } 
       } 
      } 

      if (!lblid) { 
       // assign a new label 
       lblid = labels.size(); 
       labels.push_back(new label); 
      } 
      lblinfo[y][x] = lblid; 
     } 
    } 

    // Assign indices to the labels by set and print the resulting sets 
    int maxindex = 0; 
    static const char chars[] = "abcefghijklmnopqrstuvwxyz"; 
    for (int y = 0; y < height; y++) { 
     for (int x = 0; x < width; x++) { 
      unsigned short labelid = lblinfo[y][x]; 
      if (labelid == 0) { 
       putchar(data[y][x]); 
       continue; 
      } 

      label *label = labels[labelid]; 
      int idx = label->getIndex(maxindex); 
      if (idx >= sizeof(chars) - 1) { 
       printf("\n\n Too many labels to print!\n"); 
       exit(1); 
      } 

      putchar(chars[idx]); 
     } 
     printf("\n"); 
    } 

    return 0; 
}