#include #include struct Vector2 { short x, y; }; struct Square { char val = -1; bool check = false; }; class Field { public: Field(int w, int h); ~Field(); private: int w, h; Square *sq; public: Square* Get(int x, int y); bool isField(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]; } bool Field::isField(int x, int y) { if(x < 0) return false; if(y < 0) return false; if(x >= w) return false; if(y >= h) return false; return true; } 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'; 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; const Vector2 d[4] = { {-1, 0}, { 1, 0}, { 0, -1}, { 0, 1} }; for(int i = 0; i < 4; i++) { if(!f.isField(x + d[i].x, y + d[i].y)) continue; Square *to = f.Get(x + d[i].x, y + d[i].y); if(to->val && !to->check) { Vector2 v; v.x = x; v.y = y; history.push_back(v); s = to; x += d[i].x; y += d[i].y; next = true; break; } } if(next) continue; if(history.empty()) break; Vector2 v = history.back(); s = f.Get(v.x, v.y); x = v.x; y = v.y; history.pop_back(); } count++; } } printf("%d\n", count); return 0; }