test/aoj/0558.test.cpp

• View this file on GitHub
• Last update: 2023-01-18 16:13:28+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0558

Depends on

• グリッド (graph/grid.hpp)

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0558"
#include <iostream>
#include <queue>

#include "graph/grid.hpp"

int main() {
    int h, w, n;
    std::cin >> h >> w >> n;
    grid::set_bound(h, w);
    std::vector<std::string> s(h);
    std::vector<grid> p(n + 1);
    for (int y = 0; y < h; y++) {
        std::cin >> s[y];
        for (int x = 0; x < w; x++) {
            if (s[y][x] == 'S') p[0] = grid(y, x);
            if (std::isdigit(s[y][x])) p[s[y][x] - '0'] = grid(y, x);
        }
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        std::vector<int> d(h * w, -1);
        std::queue<grid> q;
        d[p[i]] = 0, q.push(p[i]);
        while (!q.empty()) {
            grid u = q.front();
            q.pop();
            for (grid v : u.neighbors()) {
                if (s[v.y][v.x] == 'X') continue;
                if (d[v] != -1) continue;
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
        ans += d[p[i + 1]];
    }
    std::cout << ans << '\n';
}

#line 1 "test/aoj/0558.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0558"
#include <iostream>
#include <queue>

#line 2 "graph/grid.hpp"
#include <vector>
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/0558.test.cpp"

int main() {
    int h, w, n;
    std::cin >> h >> w >> n;
    grid::set_bound(h, w);
    std::vector<std::string> s(h);
    std::vector<grid> p(n + 1);
    for (int y = 0; y < h; y++) {
        std::cin >> s[y];
        for (int x = 0; x < w; x++) {
            if (s[y][x] == 'S') p[0] = grid(y, x);
            if (std::isdigit(s[y][x])) p[s[y][x] - '0'] = grid(y, x);
        }
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        std::vector<int> d(h * w, -1);
        std::queue<grid> q;
        d[p[i]] = 0, q.push(p[i]);
        while (!q.empty()) {
            grid u = q.front();
            q.pop();
            for (grid v : u.neighbors()) {
                if (s[v.y][v.x] == 'X') continue;
                if (d[v] != -1) continue;
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
        ans += d[p[i + 1]];
    }
    std::cout << ans << '\n';
}

Back to top page