Mysterious Maze (AOJ2325)

ちょっと嵌ってしまった

迷路があり,はじめ北を向いている.曲がれボタンとすすめボタンがあって好きな順で押せるが,曲がれボタンをi番目におした時右か左に曲がるかは決まっている.曲がれボタンを押し切った時にゴールにたどり着けるか?
迷路1000*1000 曲がれボタン押せる回数<=10^6

マスx,yでdを向ける は時間に対し単調でないが,マスx,yにいられる の方は単調(一旦行けばその後もそう) 新しい状態に移りうる奴しか見ない みたいなことをしないと計算量がオワコンするので,i回目に曲がった時に新しい状態にたどり着けるやつ ってのを考えながら(つまり前回このむきを向いたより後全てで新しく辿り着いたマス)やればよい

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
int H,W,N;
string o,s[1000];
bool vis[1000][1000];
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
bool is(int x,int y){
	return 0<=x&&x<H&&0<=y&&y<W&&s[x][y]!='#';
}
typedef pair<int,int> P;
vector<P> vc[1000001];
int main(){
	while(true){
		cin>>H>>W>>N;
		if(H==0) break;
		rep(i,N+1) vc[i].clear();
		rep(i,H) rep(j,W) vis[i][j]=0;
		cin>>o;
		rep(i,H) cin>>s[i];
		rep(i,H) rep(j,W) if(s[i][j]=='S'){
			int x=i,y=j;
			while(is(x,y)){
				vc[0].pb(P(x,y)),vis[x][y]=1;
				x--;
			}
		}
		int e[4]={0,-1,-1,-1};
		int D=0;
		rep1(i,N){
			D=(D+(o[i-1]=='L'?1:3))%4;
			for(int j=e[D]+1;j<i;j++){
				for(P p:vc[j]){
					int x=p.fs+dx[D],y=p.sc+dy[D];
					while(is(x,y)&&!vis[x][y]){
						vis[x][y]=1;
						vc[i].pb(P(x,y));
						x+=dx[D],y+=dy[D];
					}
				}
			}
			e[D]=i;
		}
		rep(i,H) rep(j,W) if(s[i][j]=='G'){
			if(vis[i][j]) puts("Yes");
			else puts("No");
		}
	}
}