如何有效地查找二維數組中的區域？

Question

我需要一個想法如何在二維數組中有效地找到標記爲0的區域。應該指出的是，還有其他的區域，比如這張圖片顯示了兩個誰擁有座標（0.0），另一個擁有座標（21.3）。

00000000000111110000111 
00000000001111110000111 
00000000011111100000111 
00000000000111000001101 
00000000011100000011101 
00000001111100001111001 
00000111111111011111001 
00000001111100001111001 
00000000010000000011001 
00000000000000000001111 

當然，真正的數組會更大。 遞歸版本，去所有方面，並停在標記1或陣列一側不夠快。

Answer 1

它看起來像你正在尋找一個flood-fill algorithm。我鏈接的維基百科頁面列出了一些可能比明顯的遞歸方法更快的算法。

如果您要查找的區域與整個陣列相比較小，則填充填充效果會很好，並且您無需搜索全部。如果您需要了解大多數或所有這些算法，那麼使用基於聯合合併的connected component labeling算法以單次計算它們可能是更好的選擇。下面是一些實現這樣的算法（請注意，我改變了它在單次運行）代碼：

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