#2196935

Solution for 2212: Stolen Jewel by ei1333

Source Code Status Test Cases
    Policy: public     Reviewed: 24    
00.06 sec    3588 KB    182 lines     3869 bytes    2017-02-23 00:31
#include<bits/stdc++.h>

using namespace std;

struct TrieNode
{
  int nxt[27];

  int exist; // ???????????\???????????¨????????????????????°???????¨?
  vector< int > accept; // ???????????????id

  TrieNode() : exist(0)
  {
    memset(nxt, -1, sizeof(nxt));
  }
};

struct Trie
{
  vector< TrieNode > nodes;
  int root;

  Trie() : root(0)
  {
    nodes.push_back(TrieNode());
  }

  virtual void direct_action(int node, int id) {}

  virtual void child_action(int node, int child, int id) {}

  void update_direct(int node, int id)
  {
    nodes[node].accept.push_back(id);
    direct_action(node, id);
  }

  void update_child(int node, int child, int id)
  {
    ++nodes[node].exist;
    child_action(node, child, id);
  }

  void add(const string &str, int str_index, int node_index, int id)
  {
    if(str_index == str.size()) {
      update_direct(node_index, id);
    } else {
      const int c = str[str_index] - 'A';
      if(nodes[node_index].nxt[c] == -1) {
        nodes[node_index].nxt[c] = (int) nodes.size();
        nodes.push_back(TrieNode());
      }
      add(str, str_index + 1, nodes[node_index].nxt[c], id);
      update_child(node_index, nodes[node_index].nxt[c], id);
    }
  }

  void add(const string &str, int id)
  {
    add(str, 0, 0, id);
  }

  void add(const string &str)
  {
    add(str, nodes[0].exist);
  }

  int size()
  {
    return (nodes[0].exist);
  }

  int nodesize()
  {
    return ((int) nodes.size());
  }
};

struct Aho_Corasick : Trie
{
  static const int FAIL = 26;
  vector< int > correct;

  Aho_Corasick() : Trie() {}

  void build()
  {
    correct.resize(nodes.size());
    for(int i = 0; i < nodes.size(); i++) {
      correct[i] = (int) nodes[i].accept.size();
    }

    queue< int > que;
    for(int i = 0; i < 27; i++) {
      if(~nodes[0].nxt[i]) {
        nodes[nodes[0].nxt[i]].nxt[FAIL] = 0;
        que.emplace(nodes[0].nxt[i]);
      } else {
        nodes[0].nxt[i] = 0;
      }
    }
    while(!que.empty()) {
      TrieNode &now = nodes[que.front()];
      correct[que.front()] += correct[now.nxt[FAIL]];
      que.pop();
      for(int i = 0; i < 26; i++) {
        if(now.nxt[i] == -1) continue;
        int fail = now.nxt[FAIL];
        while(nodes[fail].nxt[i] == -1) {
          fail = nodes[fail].nxt[FAIL];
        }
        nodes[now.nxt[i]].nxt[FAIL] = nodes[fail].nxt[i];
        que.emplace(now.nxt[i]);
      }

    }
  }

  int move(const string &str, int now = 0)
  {
    for(auto &c : str) {
      while(nodes[now].nxt[c - 'A'] == -1) now = nodes[now].nxt[FAIL];
      now = nodes[now].nxt[c - 'A'];
      if(correct[now]) return (-1);
    }
    return (now);
  }
};

const int vy[] = {-1, 0, 1, 0}, vx[] = {0, 1, 0, -1};
const string tt = "URDL";

int H, W, P;
string S[50], pat[10];

int bfs()
{
  Aho_Corasick aho;
  queue< tuple< int, int, int > > que;
  vector< int > v[50][50];

  for(int i = 0; i < P; i++) aho.add(pat[i]);
  aho.build();

  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W; j++) {
      v[i][j].resize(aho.nodesize(), -1);
      if(S[i][j] == 'S') {
        que.emplace(i, j, 0);
        v[i][j][0] = 0;
      }
    }
  }

  while(!que.empty()) {
    int y, x, now;
    tie(y, x, now) = que.front();
    que.pop();
    if(S[y][x] == 'G') return (v[y][x][now]);
    for(int i = 0; i < 4; i++) {
      int ny = y + vy[i], nx = x + vx[i];
      if(ny < 0 || nx < 0 || nx >= W || ny >= H || S[ny][nx] == '#') continue;
      int nt = aho.move(string(1, tt[i]), now);
      if(nt == -1 || ~v[ny][nx][nt]) continue;
      v[ny][nx][nt] = v[y][x][now] + 1;
      que.emplace(ny, nx, nt);
    }
  }
  return (-1);
}

int main()
{
  while(cin >> H >> W, H) {
    for(int i = 0; i < H; i++) cin >> S[i];
    cin >> P;
    for(int i = 0; i < P; i++) cin >> pat[i];
    cout << bfs() << endl;
  }
}

Compile Error Logs:
You are not authorized to see the message.

Status
Judge: 1/1 C++11 CPU: 00.06 sec Memory: 3588 KB Length: 3869 B 2017-02-23 00:31 2017-02-23 00:31
Results for testcases
Case # Verdict CPU Time Memory In Out Case Name
Case #1: : Accepted 00.06 sec 3588 KB
< prev | / | next >  
 
Judge Input #  ( | ) Judge Output #  ( | )


Comments
 
 Under Construction.
 
Categories
 
 
Free Tags