İki boyutlu dizide alanları nasıl etkili bir şekilde bulabilirsiniz?

Question

Aşağıdaki iki boyutlu dizide 0 ile işaretli alanların nasıl etkili bir şekilde bulunacağına dair bir fikre ihtiyacım var. Bu resim gibi diğer alanların da, koordinat (0.0) ve diğerinin koordine (21.3) sahip iki kişiden birini gösterdiği belirtilmelidir.

00000000000111110000111 
00000000001111110000111 
00000000011111100000111 
00000000000111000001101 
00000000011100000011101 
00000001111100001111001 
00000111111111011111001 
00000001111100001111001 
00000000010000000011001 
00000000000000000001111 

Elbette gerçek bir dizi çok daha büyük olacaktır. Her yöne giden ve işaret 1 veya dizi tarafında duran durgun sürüm yeterince hızlı değil.

Answer 1

flood-fill algorithm ürününe bakıyorsunuz. Bağladığım wikipedia sayfası, bariz özyineleme yönteminden daha hızlı olabilecek birkaç algoritmayı listeler.

Flood-fill, aradığınız alanlar dizinin tamamına göre küçükse ve bunlardan tüm aramasını yapmanız gerekmiyorsa iyi bir eşleşme olacaktır. Bunların çoğunu ya da tümünü bilmeniz gerekiyorsa, bunları bir araya getirmek için sendika birleştirmeyi temel alan bir connected component labeling algoritması kullanarak tek bir çekimde hesaplamak daha iyi bir seçenek olabilir. İşte (tek bir geçişte çalışacak şekilde deđiţtirdiđiniz notu) bu tür bir algoritma uygulayan bazı kod:

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