#include #include struct Square { char val = -1; bool check = false; Square *to[4] = {nullptr}; }; class Field { public: Field(int w, int h); ~Field(); private: int w, h; Square *sq; public: Square* Get(int x, int y); }; Field::Field(int w, int h) { this->w = w; this->h = h; sq = new Square[w * h]; } Field::~Field() { delete[] sq; } Square* Field::Get(int x, int y) { return &sq[x + y * w]; } int main(void) { int w, h; scanf("%d %d", &h, &w); getchar(); Field f(w, h); int zeros = 0; for(int y = 0; y < h; y++){ for(int x = 0; x < w; x++){ Square *s = f.Get(x, y); s->val = getchar() - '0'; s->to[0] = (x >= 1)? f.Get(x - 1, y):nullptr; s->to[1] = (x < (w - 1))? f.Get(x + 1, y):nullptr; s->to[2] = (y >= 1)? f.Get(x, y - 1):nullptr; s->to[3] = (y < (h - 1))? f.Get(x, y + 1):nullptr; if(s->val == 0) zeros++; getchar(); } } int *min = (w < h)? &w:&h; if(*min > zeros) { printf("1\n"); return 0; } int count = 0; for(int y = 0; y < h; y++){ for(int x = 0; x < w; x++){ Square *s = f.Get(x, y); if(s->check) continue; if(s->val != 1) continue; std::list history; while(1) { s->check = true; bool next = false; for(int i = 0; i < 4; i++) { if(s->to[i] && s->to[i]->val && !s->to[i]->check) { history.push_back(s); s = s->to[i]; next = true; break; } } if(next) continue; if(history.empty()) break; s = history.back(); history.pop_back(); } count++; } } printf("%d\n", count); return 0; }