#include using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) begin(v),end(v) template inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; } template inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; } using ll = long long; using pii = pair; constexpr ll INF = 1ll<<30; constexpr ll longINF = 1ll<<60; constexpr ll MOD = 1000000007; constexpr bool debug = false; //---------------------------------// #include #include #include #include struct UnionFind { public: using size_type = std::size_t; private: size_type n; std::vector dat; public: UnionFind(size_type n) : n(n), dat(n, -1) {} size_type size(size_type x) { assert(x < n); return -dat[find(x)]; } size_type find(size_type x) { assert(x < n); if (dat[x] < 0) return x; return dat[x] = find(dat[x]); } void unite(size_type x, size_type y) { assert(x < n); assert(y < n); x = find(x); y = find(y); if (x == y) return; if (dat[x] < dat[y]) std::swap(x, y); dat[y] += dat[x]; dat[x] = y; } bool issame(size_type x, size_type y) { assert(x < n); assert(y < n); return find(x) == find(y); } }; int main() { int H, W; cin >> H >> W; vector A(H, vector(W, false)); REP(i, H) REP(j, W) { int a; scanf("%d", &a); A[i][j] = a; } UnionFind uf(H * W); constexpr int dx[]{1,0,-1,0}, dy[]{0,-1,0,1}; REP(i, H) REP(j, W) { if (!A[i][j]) continue; REP(k, 4) { const int y = i + dy[k], x = j + dx[k]; if (y < 0 || y >= H || x < 0 || x >= W) continue; if (!A[y][x]) continue; uf.unite(i * W + j, y * W + x); } } int ans = 0; REP(i, H) REP(j, W) if (A[i][j] == 1 && uf.find(i * W + j) == i * W + j) ++ans; cout << ans << endl; }