#line 1 "src/test/verify/yuki-697.test.cpp" #define PROBLEM "https://yukicoder.me/problems/no/697" #line 2 "src/template.hpp" /** * @brief テンプレート * @docs docs/template.md */ // #pragma GCC target("avx2") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #include using namespace std; using ll = long long; using vl = vector; using vvl = vector; using vvvl = vector; using pl = pair; using vp = vector; using vvp = vector; using vs = vector; using vvs = vector; using vb = vector; using vvb = vector; using vvvb = vector; using vd = vector; using vvd = vector; using vvvd = vector; #define _overload3(_1, _2, _3, name, ...) name #define _rep(i, n) repi(i, 0, n) #define repi(i, a, b) for(ll i = ll(a); i < ll(b); ++i) #define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__) #define all(x) std::begin(x), std::end(x) #define make_unique(v) v.erase(unique(all(v)), v.end()); #define sum(...) accumulate(all(__VA_ARGS__), 0LL) constexpr ll inf = 0x1fffffffffffffffLL; template void input(vector &v1, vector &v2){ rep(i, v1.size()) cin >> v1[i] >> v2[i]; } template void input(vector &v1, vector &v2, vector &v3) { rep(i, v1.size()) cin >> v1[i] >> v2[i] >> v3[i]; } template void input(vector &v1, vector &v2, vector &v3, vector &v4) { rep(i, v1.size()) cin >> v1[i] >> v2[i] >> v3[i] >> v4[i]; } template istream &operator>>(istream &is, vector &v) { for(auto &x : v) { is >> x; } return is; } template ostream &operator<<(ostream &os, const vector &v) { for(int i = 0; i < (int)v.size(); i++) { if(i != (int)v.size() - 1) os << v[i] << " "; else os << v[i]; } return os; } template istream &operator>>(istream &is, pair &p) { is >> p.first >> p.second; return is; } template ostream &operator<<(ostream &os, pair &p) { os << p.first << " " << p.second; return os; } template auto vec(T x, int arg, Args... args) { if constexpr(sizeof...(args) == 0) return vector(arg, x); else return vector(arg, vec(x, args...)); } template auto min(const T &a) { return *min_element(all(a)); } template auto max(const T &a) { return *max_element(all(a)); } template bool chmin(T &a, const T &b) { return a > b ? a = b, true : false; } template bool chmax(T &a, const T &b) { return a < b ? a = b, true : false; } constexpr ll bit(ll x){ return 1LL << x; } constexpr ll msk(ll x){ return (1LL << x) - 1;} constexpr bool stand(ll x, int i) { return x & bit(i); } struct IoSetup { IoSetup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); } } iosetup; #line 2 "src/Util/grid2d.hpp" /** * @brief Grid(2D) * @docs docs/grid2d.md */ template struct Grid2D{ int H, W; vector> data; vector dx = {1, -1, 0, 0, 1, -1, 1, -1}; vector dy = {0, 0, 1, -1, 1, -1, -1, 1}; Grid2D(int H, int W) : H(H), W(W), data(H, vector(W)) {} Grid2D(int H, int W, T x) : H(H), W(W), data(H, vector(W, x)) {} Grid2D(const vector> &data) : H(data.size()), W(data[0].size()), data(data) {} vector &operator[](int i){ return data[i]; } void read(){ for(int i = 0; i < H; i++){ for(int j = 0; j < W; j++){ cin >> data[i][j]; } } } bool in(int i, int j){ return 0 <= i && i < H && 0 <= j && j < W; } int encode(int i, int j){ return i * W + j; } pair decode(int x){ return make_pair(x / W, x % W); } vector> next4(int i, int j){ return next(i, j, 4); } vector> next8(int i, int j){ return next(i, j, 8); } private: vector> next(int i, int j, int k){ vector> res; for(int t = 0; t < k; t++){ int ni = i + dx[t], nj = j + dy[t]; if(in(ni, nj)) res.push_back(make_pair(ni, nj)); } return res; } }; #line 2 "src/DataStructure/union-find.hpp" /** * @brief Union-Find * @docs docs/union-find.md */ struct UnionFind { vector par; UnionFind(int n) { par.assign(n, -1); }; int root(int x) { if(par[x] < 0) return x; else return par[x] = root(par[x]); } int size(int x) { x = root(x); return -1 * par[x]; } bool unite(int x, int y) { x = root(x); y = root(y); if(x == y) return false; if(size(x) < size(y)) swap(x, y); par[x] += par[y]; par[y] = x; return true; } bool same(int x, int y) { return root(x) == root(y); } vector leaders(){ vector res; for(int i = 0; i < (int)par.size(); i++){ if(par[i] < 0) res.push_back(i); } return res; } }; #line 5 "src/test/verify/yuki-697.test.cpp" int main(){ ll H, W; cin >> H >> W; Grid2D grid(H, W); grid.read(); UnionFind uf(H * W); for(int i = 0; i < H; i++){ for(int j = 0; j < W; j++){ for(auto [ni, nj] : grid.next4(i, j)){ if(grid[i][j] == grid[ni][nj]){ uf.unite(grid.encode(i, j), grid.encode(ni, nj)); } } } } ll ans = 0; for(auto i : uf.leaders()){ auto [nx, ny] = grid.decode(i); if(grid[nx][ny] == 1) ans++; } cout << ans << endl; }