test/aoj/1160.test.cpp

View this file on GitHub
Last update: 2023-03-05 19:05:08+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/problems/1160

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/1160"
#include <iostream>

#include "datastructure/unionfind.hpp"
#include "graph/grid.hpp"
int main() {
    while (true) {
        int w, h;
        std::cin >> w >> h;
        if (h == 0 && w == 0) break;
        grid::set_bound(h, w);
        std::vector c(h, std::vector<int>(w));
        for (int y = 0; y < h; y++) {
            for (int x = 0; x < w; x++) {
                std::cin >> c[y][x];
            }
        }
        unionfind uf(h * w);
        for (grid u : grid::grids()) {
            if (c[u.y][u.x] != 1) continue;
            for (grid v : u.neighbors_8()) {
                if (c[v.y][v.x] != 1) continue;
                uf.unite(u, v);
            }
        }
        int ans = 0;
        for (grid u : grid::grids()) {
            if (c[u.y][u.x] == 1 && uf.root(u) == int(u)) {
                ans++;
            }
        }
        std::cout << ans << '\n';
    }
}

#line 1 "test/aoj/1160.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/1160"
#include <iostream>

#line 2 "datastructure/unionfind.hpp"
#include <algorithm>
#include <vector>
struct unionfind {
    int n;
    std::vector<int> data;
    unionfind(int _n) : n(_n), data(_n, -1) {
    }
    int root(int x) {
        return (data[x] < 0) ? x : data[x] = root(data[x]);
    }
    bool unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x != y) {
            if (data[y] < data[x]) std::swap(x, y);
            data[x] += data[y];
            data[y] = x;
        }
        return x != y;
    }
    bool find(int x, int y) {
        return root(x) == root(y);
    }
    int size(int x) {
        return -data[root(x)];
    }
    std::vector<std::vector<int>> groups() {
        std::vector<int> root_buf(n), group_size(n);
        for (int i = 0; i < n; i++) {
            root_buf[i] = root(i);
            group_size[root_buf[i]]++;
        }
        std::vector<std::vector<int>> ret(n);
        for (int i = 0; i < n; i++) {
            ret[i].reserve(group_size[i]);
        }
        for (int i = 0; i < n; i++) {
            ret[root_buf[i]].push_back(i);
        }
        ret.erase(std::remove_if(
                      ret.begin(), ret.end(),
                      [&](const std::vector<int>& v) { return v.empty(); }),
                  ret.end());
        return ret;
    }
};
#line 3 "graph/grid.hpp"
struct grid {
public:
    int y, x;
    grid() {
    }
    grid(int y, int x) : y(y), x(x) {
    }
    static void set_bound(int height, int width) {
        _min_y = 0;
        _min_x = 0;
        _max_y = height - 1;
        _max_x = width - 1;
    }
    static void set_bound(int min_y, int min_x, int max_y, int max_x) {
        _min_y = min_y;
        _min_x = min_x;
        _max_y = max_y;
        _max_x = max_x;
    }
    static std::vector<grid> grids() {
        std::vector<grid> ret;
        for (int y = _min_y; y <= _max_y; y++) {
            for (int x = _min_x; x <= _max_x; x++) {
                ret.emplace_back(y, x);
            }
        }
        return ret;
    }
    static grid from(int i) {
        return grid(i / (_max_x - _min_x + 1) + _min_y,
                    i % (_max_x - _min_x + 1) + _min_x);
    }
    bool is_valid() {
        return _min_y <= y && y <= _max_y && _min_x <= x && x <= _max_x;
    }
    std::vector<grid> neighbors() {
        std::vector<grid> ret;
        for (auto [dy, dx] : grid::delta) {
            if (grid(y + dy, x + dx).is_valid()) {
                ret.emplace_back(y + dy, x + dx);
            }
        }
        return ret;
    }
    std::vector<grid> neighbors_8() {
        std::vector<grid> ret;
        for (auto [dy, dx] : grid::delta_8) {
            if (grid(y + dy, x + dx).is_valid()) {
                ret.emplace_back(y + dy, x + dx);
            }
        }
        return ret;
    }
    operator int() const {
        return (y - _min_y) * (_max_x - _min_x + 1) + (x - _min_x);
    }

private:
    static inline int _min_y, _min_x, _max_y, _max_x;
    static inline const std::vector<std::pair<int, int>> delta = {
        {0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    static inline const std::vector<std::pair<int, int>> delta_8 = {
        {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}};
};
#line 6 "test/aoj/1160.test.cpp"
int main() {
    while (true) {
        int w, h;
        std::cin >> w >> h;
        if (h == 0 && w == 0) break;
        grid::set_bound(h, w);
        std::vector c(h, std::vector<int>(w));
        for (int y = 0; y < h; y++) {
            for (int x = 0; x < w; x++) {
                std::cin >> c[y][x];
            }
        }
        unionfind uf(h * w);
        for (grid u : grid::grids()) {
            if (c[u.y][u.x] != 1) continue;
            for (grid v : u.neighbors_8()) {
                if (c[v.y][v.x] != 1) continue;
                uf.unite(u, v);
            }
        }
        int ans = 0;
        for (grid u : grid::grids()) {
            if (c[u.y][u.x] == 1 && uf.root(u) == int(u)) {
                ans++;
            }
        }
        std::cout << ans << '\n';
    }
}