test/AOJ/2212.test.cpp

View this file on GitHub
Last update: 2025-11-24 18:49:07+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2212

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2212"
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (n); i++)

#include "library/graph/Grid.hpp"
#include "library/sequence/AhoCorasick.hpp"

const std::map<char, int> mp{{'D', 0}, {'R', 1}, {'U', 2}, {'L', 3}};

int solve(int h, int w) {
    std::vector<std::string> s(h);
    REP (i, h)
        std::cin >> s[i];

    Grid<char> GR(s, '#');
    int S = GR.find('S'), T = GR.find('G');
    auto &G = GR.G;

    AhoCorasick<char, 4> AC;
    int m;
    std::cin >> m;
    REP (_, m) {
        std::string t;
        std::cin >> t;
        std::vector<char> tt(t.size());
        REP (i, t.size())
            tt[i] = mp.at(t[i]);
        AC.add(tt);
    }
    AC.build();

    std::vector dp(h * w, std::vector<int>(AC.size(), -1));
    std::queue<std::pair<int, int>> que;
    que.emplace(S, 0);
    dp[S][0] = 0;
    while (que.size()) {
        auto [idx, now] = que.front();
        que.pop();
        for (auto &e : G[idx]) {
            int nxt = AC.nxt(now, e.weight);
            if (AC.val(nxt))
                continue;
            if (dp[e.to][nxt] < 0) {
                dp[e.to][nxt] = dp[idx][now] + 1;
                que.emplace(e.to, nxt);
            }
            if (e.to == T)
                return dp[e.to][nxt];
        }
    }
    return -1;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int h, w;
    while (std::cin >> h >> w, h)
        std::cout << solve(h, w) << "\n";
}

#line 1 "test/AOJ/2212.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2212"
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (n); i++)

#line 2 "library/graph/WeightedGraph.hpp"
template <typename T> struct WeightedEdge {
    WeightedEdge() = default;
    WeightedEdge(int from, int to, T weight)
        : from(from), to(to), weight(weight) {}
    int from, to;
    T weight;
    operator int() const { return to; }
};

template <typename T> struct WeightedGraph {
    int n;
    using weight_type = T;
    using edge_type = WeightedEdge<T>;
    std::vector<edge_type> edges;

  protected:
    std::vector<int> in_deg;
    bool prepared;
    class OutgoingEdges {
        WeightedGraph *g;
        int l, r;

      public:
        OutgoingEdges(WeightedGraph *g, int l, int r) : g(g), l(l), r(r) {}
        edge_type *begin() { return &(g->edges[l]); }
        edge_type *end() { return &(g->edges[r]); }
        edge_type &operator[](int i) { return g->edges[l + i]; }
        int size() const { return r - l; }
    };
    class ConstOutgoingEdges {
        const WeightedGraph *g;
        int l, r;

      public:
        ConstOutgoingEdges(const WeightedGraph *g, int l, int r)
            : g(g), l(l), r(r) {}
        const edge_type *begin() const { return &(g->edges[l]); }
        const edge_type *end() const { return &(g->edges[r]); }
        const edge_type &operator[](int i) const { return g->edges[l + i]; }
        int size() const { return r - l; }
    };

  public:
    OutgoingEdges operator[](int v) {
        assert(prepared);
        return {this, in_deg[v], in_deg[v + 1]};
    }
    const ConstOutgoingEdges operator[](int v) const {
        assert(prepared);
        return {this, in_deg[v], in_deg[v + 1]};
    }

    bool is_prepared() const { return prepared; }

    WeightedGraph() : n(0), in_deg(1, 0), prepared(false) {}
    WeightedGraph(int n) : n(n), in_deg(n + 1, 0), prepared(false) {}
    WeightedGraph(int n, int m, bool directed = false, int indexed = 1)
        : n(n), in_deg(n + 1, 0), prepared(false) {
        scan(m, directed, indexed);
    }

    void resize(int n) { n = n; }

    void add_arc(int from, int to, T weight) {
        assert(!prepared);
        assert(0 <= from and from < n and 0 <= to and to < n);
        edges.emplace_back(from, to, weight);
        in_deg[from + 1]++;
    }
    void add_edge(int u, int v, T weight) {
        add_arc(u, v, weight);
        add_arc(v, u, weight);
    }
    void add_arc(const edge_type &e) { add_arc(e.from, e.to, e.weight); }
    void add_edge(const edge_type &e) { add_edge(e.from, e.to, e.weight); }

    void scan(int m, bool directed = false, int indexed = 1) {
        edges.reserve(directed ? m : 2 * m);
        while (m--) {
            int u, v;
            std::cin >> u >> v;
            u -= indexed;
            v -= indexed;
            T weight;
            std::cin >> weight;
            if (directed)
                add_arc(u, v, weight);
            else
                add_edge(u, v, weight);
        }
        build();
    }

    void build() {
        assert(!prepared);
        prepared = true;
        for (int v = 0; v < n; v++)
            in_deg[v + 1] += in_deg[v];
        std::vector<edge_type> new_edges(in_deg.back());
        auto counter = in_deg;
        for (auto &&e : edges)
            new_edges[counter[e.from]++] = e;
        edges = new_edges;
    }

    void graph_debug() const {
#ifndef __DEBUG
        return;
#endif
        assert(prepared);
        for (int from = 0; from < n; from++) {
            std::cerr << from << ";";
            for (int i = in_deg[from]; i < in_deg[from + 1]; i++)
                std::cerr << "(" << edges[i].to << "," << edges[i].weight
                          << ")";
            std::cerr << "\n";
        }
    }
};
#line 3 "library/graph/Grid.hpp"
#define REP_(i, n) for (int i = 0; i < (n); i++)
template <typename T> class Grid {
    const int h, w;
    std::optional<T> ban;
    // D,R,U,L
    static constexpr std::pair<int, int> d4[4] = {
        {1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    template <typename vecvecT> void build(const vecvecT &grid) {
        REP_(y, h) REP_(x, w) {
            int p = id(y, x);
            v[p] = grid[y][x];
            if (ban and v[p] == ban.value())
                continue;
            REP_(d, 4) {
                int y2 = y + d4[d].first, x2 = x + d4[d].second;
                if (in(y2, x2) and (!ban or ban.value() != grid[y2][x2]))
                    G.add_arc(p, id(y2, x2), d);
            }
        }
        G.build();
    }

  public:
    std::vector<T> v;
    WeightedGraph<int> G;
    bool in(int y, int x) const {
        return 0 <= y and y < h and 0 <= x and x < w;
    }
    int id(int y, int x) const {
        assert(in(y, x));
        return y * w + x;
    }
    std::pair<int, int> r2(int a) const {
        assert(0 <= a and a < h * w);
        return {a / w, a % w};
    }

    Grid(const std::vector<std::vector<T>> &grid,
         const std::optional<T> &ban = std::nullopt)
        : h(grid.size()), w(grid[0].size()), ban(ban), v(h * w), G(h * w) {
        build(grid);
    }
    Grid(const std::vector<std::string> &s,
         const std::optional<T> &ban = std::nullopt)
        : h(s.size()), w(s[0].size()), ban(ban), v(h * w), G(h * w) {
        static_assert(std::is_same<T, char>::value, "value_type==char");
        build(s);
    }

    int find(const T &c) const {
        REP_(i, h * w) if (v[i] == c) return i;
        return -1;
    }
};
#undef REP_
#line 2 "library/algebra/group/Add.hpp"
template<typename X>
struct GroupAdd {
  using value_type = X;
  static constexpr X op(const X &x, const X &y) noexcept { return x + y; }
  static constexpr void Rchop(X&x, const X&y){ x+=y; }
  static constexpr void Lchop(const X&x, X&y){ y+=x; }
  static constexpr X inverse(const X &x) noexcept { return -x; }
  static constexpr X power(const X &x, long long n) noexcept { return X(n) * x; }
  static constexpr X unit() { return X(0); }
  static constexpr bool commute = true;
};
#line 2 "library/sequence/ForString.hpp"
template <char MARGIN> struct ForString {
    static constexpr char change(char c) { return c - MARGIN; }
    static constexpr char restore(char a) { return a + MARGIN; }

    static std::vector<char> change(const std::string &s) {
        std::vector<char> v(s.size());
        for (int i = 0; i < s.size(); i++)
            v[i] = change(s[i]);
        return v;
    }
    static std::string restore(const std::vector<char> &v) {
        std::string s(v.size(), '#');
        for (int i = 0; i < v.size(); i++)
            s[i] = restore(v[i]);
        return s;
    }
};
struct FSAa {
    static constexpr char change(char c) {
        return c <= 'Z' ? c - 'A' : 26 + c - 'a';
    }
    static constexpr char restore(char a) {
        return a < 26 ? 'A' : a - 26 + 'a';
    }
    static std::vector<char> change(const std::string &s) {
        std::vector<char> v(s.size());
        for (int i = 0; i < s.size(); i++)
            v[i] = change(s[i]);
        return v;
    }
    static std::string restore(const std::vector<char> &v) {
        std::string s(v.size(), '#');
        for (int i = 0; i < v.size(); i++)
            s[i] = restore(v[i]);
        return s;
    }
};
using FSA = ForString<'A'>;
using FSa = ForString<'a'>;
using FS0 = ForString<'0'>;

#ifdef STR
#define STRA(s)                                                                \
    STR(s##tomato);                                                            \
    auto s = FSA::change(s##tomato);
#define STRa(s)                                                                \
    STR(s##tomato);                                                            \
    auto s = FSa::change(s##tomato);
#define STR0(s)                                                                \
    STR(s##tomato);                                                            \
    auto s = FS0::change(s##tomato);
#endif
#line 4 "library/sequence/Trie.hpp"
template <typename CHAR, int SIGMA, typename AbelMonoid = GroupAdd<int>>
class Trie {
  protected:
    using X = typename AbelMonoid::value_type;
    struct Node {
        std::array<int, SIGMA> nxt;
        int pre;
        X val, suffix_val; // suffix_val は自身を含まない
        Node(int pre)
            : pre(pre), val(AbelMonoid::unit()),
              suffix_val(AbelMonoid::unit()) {
            std::ranges::fill(nxt, -1);
        }
    };
    std::vector<Node> nodes;

  public:
    Trie() : nodes(1, Node(-1)) {}

    int &nxt(int now, const CHAR &a) { return nodes[now].nxt[a]; }
    const int &nxt(int now, const CHAR &a) const { return nodes[now].nxt[a]; }

    int add(const std::vector<CHAR> &v, X x = 1) {
        int now = 0;
        for (const CHAR &a : v) {
            assert(0 <= a and a < SIGMA);
            if (!~nxt(now, a)) {
                nxt(now, a) = nodes.size();
                nodes.emplace_back(now);
            }
            AbelMonoid::Rchop(nodes[now].suffix_val, x);
            now = nxt(now, a);
        }
        AbelMonoid::Rchop(nodes[now].val, x);
        return now;
    }
    int node_idx(const std::vector<CHAR> &v) const {
        // s の Node を返す　追加されて無ければ -1
        int now = 0;
        for (const CHAR &a : v) {
            if (!~nxt(now, a))
                return -1;
            now = nxt(now, a);
        }
        return now;
    }
    X val(const std::vector<CHAR> &v) {
        int id = node_idx(v);
        return (~id ? nodes[id].val : AbelMonoid::unit());
    }
    X &val(int node_id) { return nodes[node_id].val; }
    // vは含まない
    X prefix_prod(const std::vector<CHAR> &v) {
        int now = 0;
        X sum = AbelMonoid::unit();
        for (const CHAR &a : v) {
            if (!~nxt(now, a))
                break;
            AbelMonoid::Rchop(sum, nodes[now].val);
            now = nxt(now, a);
        }
        return sum;
    }
    // vは含まない
    X suffix_prod(const std::vector<CHAR> &v) const {
        int id = node_idx(v);
        return (~id ? nodes[id].suffix_val : AbelMonoid::unit());
    }
    std::vector<CHAR> restore(int node_id) {
        assert(0 <= node_id and node_id < nodes.size());
        std::vector<CHAR> res;
        while (~nodes[node_id].pre) {
            int pre = nodes[node_id].pre;
            for (int j = 0; j < SIGMA; j++)
                if (nxt(pre, j) == node_id) {
                    res.push_back(j);
                    break;
                }
            node_id = pre;
        }
        std::ranges::reverse(res);
        return res;
    }
    X prod() const { return nodes[0].suffix_val; }
    int size() const { return nodes.size(); }

    template <typename F>
    void query(const std::vector<CHAR> &v, const F &f, int l = 0, int r = -1) {
        if (r < 0)
            r = v.size();
        int now = 0;
        for (int i = l; i < r; i++) {
            now = nxt(now, v[i]);
            if (~now)
                f(now);
            else
                break;
        }
    }
};
#line 3 "library/sequence/AhoCorasick.hpp"
template <typename CHAR, int SIGMA, typename AbelMonoid = GroupAdd<int>>
class AhoCorasick : Trie<CHAR, SIGMA, AbelMonoid> {
    using super = Trie<CHAR, SIGMA, AbelMonoid>;
    using super::nodes;
    using X = typename AbelMonoid::value_type;
    std::vector<int> suffix;
    bool prepared;

  public:
    using super::nxt, super::add, super::node_idx, super::val,
        super::prefix_prod, super::suffix_prod, super::query, super::restore,
        super::prod, super::size;

    AhoCorasick() : prepared(false) {}

    bool is_prepared() const { return prepared; }

    void build() {
        assert(!prepared);
        prepared = true;
        suffix.resize(nodes.size());
        std::queue<int> que;
        que.push(0);
        while (que.size()) {
            int now = que.front();
            que.pop();
            for (int i = 0; i < SIGMA; i++) {
                int &nxt_id = nodes[now].nxt[i];
                if (~nxt_id) {
                    suffix[nxt_id] = (now ? nodes[suffix[now]].nxt[i] : 0);
                    AbelMonoid::Rchop(val(nxt_id), val(suffix[nxt_id]));
                    que.push(nxt_id);
                } else
                    nxt_id = (now ? nodes[suffix[now]].nxt[i] : 0);
            }
        }
    }

    X path_prod(const std::vector<CHAR> &v) {
        assert(prepared);
        X res = AbelMonoid::unit();
        int now = 0;
        for (const CHAR &a : v) {
            now = nxt(now, a);
            AbelMonoid::Rchop(res, val(now));
        }
        return res;
    }
};
#line 7 "test/AOJ/2212.test.cpp"

const std::map<char, int> mp{{'D', 0}, {'R', 1}, {'U', 2}, {'L', 3}};

int solve(int h, int w) {
    std::vector<std::string> s(h);
    REP (i, h)
        std::cin >> s[i];

    Grid<char> GR(s, '#');
    int S = GR.find('S'), T = GR.find('G');
    auto &G = GR.G;

    AhoCorasick<char, 4> AC;
    int m;
    std::cin >> m;
    REP (_, m) {
        std::string t;
        std::cin >> t;
        std::vector<char> tt(t.size());
        REP (i, t.size())
            tt[i] = mp.at(t[i]);
        AC.add(tt);
    }
    AC.build();

    std::vector dp(h * w, std::vector<int>(AC.size(), -1));
    std::queue<std::pair<int, int>> que;
    que.emplace(S, 0);
    dp[S][0] = 0;
    while (que.size()) {
        auto [idx, now] = que.front();
        que.pop();
        for (auto &e : G[idx]) {
            int nxt = AC.nxt(now, e.weight);
            if (AC.val(nxt))
                continue;
            if (dp[e.to][nxt] < 0) {
                dp[e.to][nxt] = dp[idx][now] + 1;
                que.emplace(e.to, nxt);
            }
            if (e.to == T)
                return dp[e.to][nxt];
        }
    }
    return -1;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int h, w;
    while (std::cin >> h >> w, h)
        std::cout << solve(h, w) << "\n";
}