Hashiryo's Library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub hashiryo/Library

:heavy_check_mark: test/aoj/2212.test.cpp

Depends on

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2212
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include "src/String/AhoCorasick.hpp"
using namespace std;
int main() {
 ios::sync_with_stdio(0);
 cin.tie(0);
 int di[4]= {1, 0, -1, 0};
 int dj[4]= {0, 1, 0, -1};
 char dc[4]= {'D', 'R', 'U', 'L'};
 constexpr int INF= 1 << 30;
 for (int N, M; cin >> N >> M && N;) {
  auto ij2n= [M](int i, int j) { return i * M + j; };
  auto n2ij= [M](int n) { return make_pair(n / M, n % M); };
  auto sn2m= [N, M](int s, int n) { return s * N * M + n; };
  auto m2sn= [N, M](int m) { return make_pair(m / (N * M), m % (N * M)); };
  string maze[N];
  int S, G;
  for (int i= 0; i < N; i++) {
   cin >> maze[i];
   for (int j= 0; j < M; j++) {
    if (maze[i][j] == 'S') S= ij2n(i, j);
    if (maze[i][j] == 'G') G= ij2n(i, j);
   }
  }
  int P;
  cin >> P;
  vector<string> t(P);
  for (int i= 0; i < P; i++) cin >> t[i];
  AhoCorasick ac(t);
  queue<int> que;
  int K= N * M * ac.state_size();
  int dist[K];
  fill_n(dist, K, INF);
  int m0= sn2m(ac.initial_state(), S);
  dist[m0]= 0;
  que.push(m0);
  int ans= -1;
  while (!que.empty()) {
   int m= que.front();
   que.pop();
   auto [s, n]= m2sn(m);
   if (n == G) {
    ans= dist[m];
    break;
   }
   auto [i, j]= n2ij(n);
   for (int d= 0; d < 4; d++) {
    int ni= i + di[d], nj= j + dj[d];
    if (ni < 0 || N <= ni || nj < 0 || M <= nj) continue;
    if (maze[ni][nj] == '#') continue;
    int ns= ac.transition(s, dc[d]);
    if (ac.is_accept(ns)) continue;
    int nn= ij2n(ni, nj);
    int nm= sn2m(ns, nn);
    if (dist[nm] != INF) continue;
    dist[nm]= dist[m] + 1;
    que.push(nm);
   }
  }
  cout << ans << '\n';
 }
 return 0;
}
#line 1 "test/aoj/2212.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2212
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#line 3 "src/String/AhoCorasick.hpp"
#include <algorithm>
#include <numeric>
template <class String> struct AhoCorasick {
 using symbol_t= typename String::value_type;
 AhoCorasick(const std::vector<String> &ps) {
  const size_t n= ps.size();
  std::vector<int> ord(n), rows;
  std::iota(ord.begin(), ord.end(), 0), std::sort(ord.begin(), ord.end(), [&](int l, int r) { return ps[l] < ps[r]; });
  std::vector<size_t> lcp(n, 0), prev(n, 0), cur(n);
  for (size_t i= 1, j, ed; i < n; lcp[i++]= j)
   for (j= 0, ed= std::min(ps[ord[i - 1]].size(), ps[ord[i]].size()); j < ed; j++)
    if (ps[ord[i - 1]][j] != ps[ord[i]][j]) break;
  size_t nodes= 1;
  for (size_t i= 0; i < n; i++) nodes+= ps[ord[i]].size() - lcp[i];
  bg.reserve(nodes + 1), es.reserve(nodes), match.reserve(nodes), rows.reserve(n + 1);
  for (size_t row= 0; row < n; row++)
   if (!ps[ord[row]].empty()) rows.push_back(row);
  rows.push_back(-1), bg.push_back(0), match.push_back({});
  for (size_t i= 0; i < n && ps[ord[i]].empty(); ++i) match[0].push_back(ord[i]);
  for (size_t col= 0; rows[0] != -1; col++) {
   int size= 0;
   for (int &r: rows) {
    if (r == -1) break;
    size_t row= r;
    if (size++; lcp[row] <= col) {
     if (size_t par= prev[row]; bg[par] == -1) bg[par]= es.size();
     es.push_back(ps[ord[row]][col]), bg.push_back(-1);
     if (match.push_back({}); col + 1 == ps[ord[row]].size())
      for (size_t i= row; i < n && ps[ord[i]] == ps[ord[row]]; ++i) match.back().push_back(ord[i]);
    }
    if (cur[row]= bg.size() - 1; col + 1 == ps[ord[row]].size()) r= -1;
   }
   *std::remove(rows.begin(), rows.begin() + size, -1)= -1, prev.swap(cur);
  }
  bg.push_back(es.size());
  for (size_t i= bg.size() - 1; --i;)
   if (bg[i] == -1) bg[i]= bg[i + 1];
  fail.assign(match.size(), -1);
  for (int u= 0, ed= match.size(); u < ed; u++)
   for (auto i= bg[u], v= i + 1; i < bg[u + 1]; i++, v++) {
    int r= fail[v]= transition(fail[u], es[i]);
    match[v].insert(match[v].end(), match[r].begin(), match[r].end());
   }
 }
 inline int initial_state() const { return 0; }
 inline std::vector<int> matched_patterns(int s) const { return match[s]; }
 inline bool is_accept(int s) const { return !match[s].empty(); }
 inline int transition(int s, symbol_t c) const {
  for (; s >= 0; s= fail[s])
   if (int v= next(s, c); v != -1) return v;
  return 0;
 }
 inline int state_size() const { return match.size(); }
private:
 std::vector<int> bg, fail;
 std::vector<symbol_t> es;
 std::vector<std::vector<int>> match;
 inline int next(int s, symbol_t c) const {
  int index= std::lower_bound(es.begin() + bg[s], es.begin() + bg[s + 1], c) - es.begin();
  if (index != bg[s + 1] && c == es[index]) return index + 1;
  return -1;
 }
};
#line 9 "test/aoj/2212.test.cpp"
using namespace std;
int main() {
 ios::sync_with_stdio(0);
 cin.tie(0);
 int di[4]= {1, 0, -1, 0};
 int dj[4]= {0, 1, 0, -1};
 char dc[4]= {'D', 'R', 'U', 'L'};
 constexpr int INF= 1 << 30;
 for (int N, M; cin >> N >> M && N;) {
  auto ij2n= [M](int i, int j) { return i * M + j; };
  auto n2ij= [M](int n) { return make_pair(n / M, n % M); };
  auto sn2m= [N, M](int s, int n) { return s * N * M + n; };
  auto m2sn= [N, M](int m) { return make_pair(m / (N * M), m % (N * M)); };
  string maze[N];
  int S, G;
  for (int i= 0; i < N; i++) {
   cin >> maze[i];
   for (int j= 0; j < M; j++) {
    if (maze[i][j] == 'S') S= ij2n(i, j);
    if (maze[i][j] == 'G') G= ij2n(i, j);
   }
  }
  int P;
  cin >> P;
  vector<string> t(P);
  for (int i= 0; i < P; i++) cin >> t[i];
  AhoCorasick ac(t);
  queue<int> que;
  int K= N * M * ac.state_size();
  int dist[K];
  fill_n(dist, K, INF);
  int m0= sn2m(ac.initial_state(), S);
  dist[m0]= 0;
  que.push(m0);
  int ans= -1;
  while (!que.empty()) {
   int m= que.front();
   que.pop();
   auto [s, n]= m2sn(m);
   if (n == G) {
    ans= dist[m];
    break;
   }
   auto [i, j]= n2ij(n);
   for (int d= 0; d < 4; d++) {
    int ni= i + di[d], nj= j + dj[d];
    if (ni < 0 || N <= ni || nj < 0 || M <= nj) continue;
    if (maze[ni][nj] == '#') continue;
    int ns= ac.transition(s, dc[d]);
    if (ac.is_accept(ns)) continue;
    int nn= ij2n(ni, nj);
    int nm= sn2m(ns, nn);
    if (dist[nm] != INF) continue;
    dist[nm]= dist[m] + 1;
    que.push(nm);
   }
  }
  cout << ans << '\n';
 }
 return 0;
}

Test cases

Env Name Status Elapsed Memory
g++-13 judge_data :heavy_check_mark: AC 31 ms 5 MB
clang++-18 judge_data :heavy_check_mark: AC 25 ms 5 MB
Back to top page