#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef unsigned long long ull; const ll MOD = 1000000007; #define rep(i,n) for(int i=0;i=0;i--) #define all(x) (x).begin(),(x).end() int H, W; class UnionFind { //par[i]:ノードiの親 //count[i]:iが親の時、iが属するグループのノード数 vector par; vector count; int m_groupCount = 0; public: UnionFind(int N) { par.push_back(0); count.push_back(0); m_groupCount = N; for (int i = 1; i <= N; i++) { //最初は全てが根であるとして初期化 par.push_back(i); count.push_back(1); } } //データxが属する木の根を再帰で得る:root(x) = {xの木の根} int root(int x) { if (par[x] == x) return x; //ついでに親を張り替え return par[x] = root(par[x]); } //xとyの木を併合 void unite(int x, int y) { int rx = root(x); int ry = root(y); if (rx == ry) return; //xとyの根が同じでない(=同じ木にない)時:xの根rxをyの根ryにつける par[rx] = ry; //要素数の変更 count[ry] += count[rx]; count[rx] = 0; //木の併合によってグループが1つ減る m_groupCount--; } // 2つのデータx, yが属する木が同じならtrueを返す bool same(int x, int y) { return root(x) == root(y); } //指定したデータxが属するグループの要素数を返す int size(int x) { return count[root(x)]; } //UnionFindのグループの個数を返す int groupCount() { return m_groupCount; } }; bool IsInRange(int w, int h) { return 0 <= w && w <= W - 1 && 0 <= h && h <= H - 1; } int ToIndex(int w, int h) { return h * W + w; } int main() { cin >> H >> W; vector> A(W, vector(H, 0)); rep(h, H) rep(w, W) cin >> A[w][h]; UnionFind uf(H * W); rep(h, H) { rep(w, W) { if (A[w][h] != 1) continue; int idx = ToIndex(w, h); //上と左だけ結合判定 if (IsInRange(w - 1, h) && A[w - 1][h] == 1) { int i = ToIndex(w - 1, h); uf.unite(idx, i); A[w - 1][h] = 0; } if (IsInRange(w, h - 1) && A[w][h - 1] == 1) { int i = ToIndex(w, h - 1); uf.unite(idx, i); A[w][h - 1] = 0; } } } //個数確認 //親の個数をカウント ll count = 0; rep(h, H) { rep(w, W) { if (A[w][h] != 1) continue; int idx = ToIndex(w, h); if (uf.root(idx) == idx) count++; } } cout << count << endl; return 0; }