Algoogle

Algorithm for Programming Contest

AOJ 2212 Stolen Jewel

Category: AOJ Tag: aho-corasick

Stolen Jewel

問題概要


解法


禁止パターンはAho-Corasickで検出する。 各地点の座標とそのときのTrie木の位置でBFSする。 ゴールに辿りつけなかったら-1

コード


(2212.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>

#define rep(i,a) for(int i = 0;i < (a); i++)
#define pb push_back

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pii;

struct PMA{
    PMA* next[256];     //失敗時に0を利用
    vector<int> matched;//sort済みを仮定
    PMA(){memset(next, 0, sizeof(next));}
    ~PMA(){for(int i = 0; i < 256; i++) if(next[i]) delete next[i];}
};

vector<int> set_union(const vector<int> &a,const vector<int> &b){
    vector<int> res;
    set_union(all(a), all(b), back_inserter(res));
    return res;
}

//パターンマッチングオートマトンの生成,生成元パターンをpattern, 個数をcountに代入して用いる
PMA *buildPMA(vector<string> pattern){
    PMA *root = new PMA, *now;
    root -> next[0] = root;
    //Phase1.Trie木の生成
    for(int i = 0; i < pattern.size(); i++){
        now = root;
        for(int j = 0; j < pattern[i].size(); j++){
            if(now -> next[(int)pattern[i][j]] == 0)
                now -> next[(int)pattern[i][j]] = new PMA;
            now = now -> next[(int)pattern[i][j]];
        }
        now -> matched.push_back(i);
    }
    queue<PMA*> que;
    //Phase2.BFSによるオートマトンの生成
    for(int i = 1; i < 256; i++){
        if(!root -> next[i]) root -> next[i] = root; //使われていない部分のnextをrootに
        else {
            root -> next[i] -> next[0] = root;      //失敗時はルートに戻る
            que.push(root -> next[i]);
        }
    }
    while(!que.empty()){
        now = que.front(); que.pop();
        for(int i = 1; i < 256; i++){
            if(now -> next[i]){
                PMA *next = now -> next[0];
                while(!next -> next[i]) next = next -> next[0];
                now -> next[i] -> next[0] = next -> next[i];
                now -> next[i] -> matched = set_union(now -> next[i] -> matched,
                                                      next -> next[i] -> matched);
                que.push(now -> next[i]);
            }
        }
    }
    return root;
}

void match(PMA* &pma, const string s, vector<int> &res){
    for(int i = 0; i < s.size(); i++){
        int c = s[i];
        while(!pma -> next[c])
            pma = pma -> next[0];
        pma = pma -> next[c];
        for(int j = 0; j < pma -> matched.size(); j++)
            res[pma -> matched[j]] = true;
    }
}

int h, w, n;
vector<string> table;
pii s, g;
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
string d[] = {"L","R","U","D"};

struct S{
    pii p;
    int turn;
    PMA *pma;
    string str; //debug用経路
    S(pii p, int turn, PMA *pma, string str):p(p),turn(turn),pma(pma),str(str){}
};

bool inrange(pii p){
    int x = p.first, y = p.second;
    return x >= 0 && x < w && y >= 0 && y < h;
}

int main(){
    while(cin >> h >> w, h || w){
        table.resize(h);
        rep(i,h) cin >> table[i];
        rep(i,h)rep(j,w)
            if(table[i][j] == 'S') s = pii(j,i);
            else if(table[i][j] == 'G') g = pii(j,i);
        cin >> n;
        vector<string> pattern(n);
        rep(i,n) cin >> pattern[i];
        PMA* root = buildPMA(pattern);
	
        int ans = -1;
        queue<S> que;
        que.push(S(s,0,root,""));
        set<PMA*> visited[64][64];
        while(!que.empty()){
            S t = que.front(); que.pop();
            rep(i,t.pma->matched.size()) cout << t.pma->matched[i] << endl;
            if(t.p == g){
                ans = t.turn;
                break;
            }
            rep(i,4){
                pii np = pii(t.p.first+dx[i],t.p.second+dy[i]);
                if(inrange(np) && table[np.second][np.first] != '#'){
                    PMA* next = t.pma;
                    vi res(n);
                    match(next,d[i],res);
                    bool ok = false;
                    rep(j,n) ok |= res[j];
                    if(!ok && visited[np.first][np.second].find(next) ==
                       visited[np.first][np.second].end()){
                        visited[np.first][np.second].insert(next);
                        que.push(S(np,t.turn+1,next,t.str+d[i]));
                    }
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Comments