/* -*- coding: utf-8 -*- * * 697.cc: No.697 池の数はいくつか - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_H = 3000; const int MAX_W = 3000; const int dxs[] = { 1, 0, -1, 0 }, dys[] = { 0, -1, 0, 1 }; /* typedef */ typedef pair pii; /* global variables */ bool flds[MAX_H][MAX_W], used[MAX_H][MAX_W]; /* subroutines */ /* main */ int main() { int h, w; scanf("%d%d", &h, &w); for (int y = 0; y < h; y++) for (int x = 0; x < w; x++) { int a; scanf("%d", &a); flds[y][x] = (a > 0); } int cnt = 0; for (int y = 0; y < h; y++) for (int x = 0; x < w; x++) if (flds[y][x] && ! used[y][x]) { cnt++; used[y][x] = true; queue q; q.push(pii(x, y)); while (! q.empty()) { pii u = q.front(); q.pop(); int &ux = u.first, &uy = u.second; for (int di = 0; di < 4; di++) { int vx = ux + dxs[di], vy = uy + dys[di]; if (vx >= 0 && vx < w && vy >= 0 && vy < h && flds[vy][vx] && ! used[vy][vx]) { used[vy][vx] = true; q.push(pii(vx, vy)); } } } } printf("%d\n", cnt); return 0; }