2212-Stolen Jewel

問題文

解法

Aho-Corasick法を用いてパターンに一致しないようにBFSする

実装(C++)

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <iomanip>
#include <sstream>
#include <tr1/unordered_set>
using namespace std;


#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=(x);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)

int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1}; //左 上 下 右
char d[4]={'L','U','R','D'};
struct PMA{
	PMA* next[256]; //失敗時に0を利用
	bool matched;
	char k; //Debug
	PMA(){REP(i,256)next[i]=0;matched=false;}
	~PMA(){REP(i,256)if(next[i])delete next[i];}
};
//パターンマッチングオートマトンの生成．生成元パターンをpattern,個数をcountに代入して用いる
PMA *buildPMA(string pattern[],int count){
	PMA *root=new PMA,*now;
	root->next[0]=root;
	REP(i,count){
		now=root;
		for(int j=0;j<(int)pattern[i].size();j++){
			if(now->next[(int)pattern[i][j]]==0){
				now->next[(int)pattern[i][j]]=new PMA;
				now->next[(int)pattern[i][j]]->k=pattern[i][j];
			}
			now=now->next[(int)pattern[i][j]];
		}
		now->matched|=1;
	}

	queue<PMA*> que;
	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|=(next->next[i]->matched);
				que.push(now->next[i]);
			}
		}
	}
	return root;
}

bool match(PMA* &pma,const char s){
	int c=s;
	while(!pma->next[c]){
		pma=pma->next[0];
	}
	pma=pma->next[c];
	return pma->matched;
}

typedef pair<int,int> P;
P s,g;
int H,W;
char MAP[100][100];
struct State{
	int x,y;
	int turn;
	PMA* pma;
};
tr1::unordered_set<PMA*> ac[100][100];
int main(){
	for(;cin>>H>>W;){
		if((W|H)==0)break;
		for(int i=0;i<H;i++){
			string t;
			cin>>t;
			for(int j=0;j<W;j++){
				MAP[j][i]=t[j];
				if(MAP[j][i]=='S'){
					s=P(j,i);MAP[j][i]='.';
				}else if(MAP[j][i]=='G'){
					g=P(j,i);MAP[j][i]='.';
				}
				ac[j][i].clear();
			}
		}
		int n;
		cin>>n;
		string pat[n];
		REP(i,n){
			cin>>pat[i];
		}
		PMA *root=buildPMA(pat,n);
		queue<State> que;
		int ans=-1;
		que.push((State){s.first,s.second,0,root});
		while(!que.empty()){
			State t=que.front();
			que.pop();
			//移動
			if(t.x==g.first&&t.y==g.second){
				ans=t.turn;
				break;
			}
			PMA* next;
			REP(k,4){
				int nx=t.x+dx[k],ny=t.y+dy[k];
				if(nx>=0&&nx<W&&ny>=0&&ny<H&&MAP[nx][ny]=='.'){
					next=t.pma;
					if(match(next,d[k])==false){
						if(ac[nx][ny].find(next)!=ac[nx][ny].end())continue;
						que.push((State){nx,ny,t.turn+1,next});
						ac[nx][ny].insert(next);
					}
				}
			}
		}
		cout<<ans<<endl;
	}
}