algorithm - How to effectively find areas in two-dimensional array? -

i need idea how find areas below marked 0 in two-dimensional array. should noted there other areas, such picture shows 1 of 2 owns coordinate (0.0) , other owns coordinate (21.3).

00000000000111110000111 00000000001111110000111 00000000011111100000111 00000000000111000001101 00000000011100000011101 00000001111100001111001 00000111111111011111001 00000001111100001111001 00000000010000000011001 00000000000000000001111 

of course real array larger. recursive version goes sides , stops @ mark 1 or array side isn't fast enough.

it looks you're looking flood-fill algorithm. wikipedia page linked lists few algorithms may faster obvious recursive method.

flood-fill match if areas you're looking small compared entire array, , don't need search all of them. if need know or of them, computing them in single shot using union-merge based connected component labeling algorithm may better choice. here's code implements such algorithm (note i've altered run in single pass):

#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() {     (int = 0; data[0][i]; i++)         width = + 1;     (int = 0; data[i]; i++) {         height = + 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 used unassigned flag      (int y = 0; y < height; y++) {         (int x = 0; x < width; x++) {             if (data[y][x] == '1')                 continue;              // try find neighboring label             unsigned short lblid = 0;             if (x != 0 && lblinfo[y][x-1] != 0)                 lblid = lblinfo[y][x-1];              // merge cells above             if (y != 0) {                 (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 new label                 lblid = labels.size();                 labels.push_back(new label);             }             lblinfo[y][x] = lblid;         }     }      // assign indices labels set , print resulting sets     int maxindex = 0;     static const char chars[] = "abcefghijklmnopqrstuvwxyz";     (int y = 0; y < height; y++) {         (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 many labels print!\n");                 exit(1);             }              putchar(chars[idx]);         }         printf("\n");     }      return 0; }