#include #include #include using namespace std; struct UnionFind { vector data; int __size; UnionFind(int size) : data(size, -1), __size(size) { } bool unionSet(int x, int y) { if ((x = root(x)) != (y = root(y))) { if (data[y] < data[x]) swap(x, y); data[x] += data[y]; data[y] = x; __size--; } return x != y; } bool findSet(int x, int y) { return root(x) == root(y); } int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); } int size(int x) { return -data[root(x)]; } int size() { return __size; } }; int main() { const int ALIVE = 1; int h, w; cin >> h >> w; vector> field(h, vector(w)); for (auto &row: field) for (auto &c: row) cin >> c; auto idx = [&](int i, int j) { return i * w + j; }; auto out_field = [&](int i, int j) { return i < 0 || i >= h || j < 0 || j >= w; }; UnionFind uf(h * w); int cnt = 0; for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) { if (field[i][j] != ALIVE) continue; cnt++; for (int di: {-1, 0, 1}) for (int dj: {-1, 0, 1}) { if (di * di + dj * dj != 1) continue; int ni = i + di, nj = j + dj; if (out_field(ni, nj) || field[ni][nj] != ALIVE) continue; if (idx(i, j) < idx(ni, nj)) uf.unionSet(idx(i, j), idx(ni, nj)); } } int cnt_wall = h * w - cnt; cout << uf.size() - cnt_wall << endl; return 0; }