AOJ 2643: AI

構文解析要素、なし

#include<stdio.h>
#include<algorithm>
using namespace std;
char str[52][52];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
char com[1100];
int vis[52][52][4][1100];
int to[1100];
int last[1100];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++)scanf("%s",str[i]);
	scanf("%s",com);
	int depth=0;
	int len=0;
	for(int i=0;com[i];i++){
		len++;
		if(com[i]=='['||com[i]=='{'){
			last[depth++]=i;
		}
		if(com[i]==']'||com[i]=='}'){	
			depth--;
			to[i]=last[depth];
			to[last[depth]]=i;
		}
	}
	int row=0;
	int col=0;
	int dir=0;
	int cur=0;
	int gr,gc;
	for(int i=0;i<a;i++)for(int j=0;j<b;j++){
		if(str[i][j]=='s'){
			row=i;col=j;
		}
		if(str[i][j]=='g'){
			gr=i;gc=j;
		}
	}
	vis[row][col][dir][0]=1;
	int ret=0;
	while(cur<len){
		if(com[cur]=='['||com[cur]=='{'){
			bool nt=false;
			bool val=false;
			char p=com[cur+1];
			if(p=='~'){
				p=com[cur+2];
				nt=true;
			}
			if(p=='N'&&dir==0)val=true;
			if(p=='E'&&dir==1)val=true;
			if(p=='S'&&dir==2)val=true;
			if(p=='W'&&dir==3)val=true;
			if(p=='C'&&str[row+dx[dir]][col+dy[dir]]=='#')val=true;
			if(p=='T')val=true;
			if(nt)val=!val;
			if(val){
				if(nt)cur+=3;
				else cur+=2;
			}else{
				cur=to[cur]+1;
			}
		}else if(com[cur]==']')cur++;
		else if(com[cur]=='}')cur=to[cur];
		else{
			if(com[cur]=='^'){
				if(str[row+dx[dir]][col+dy[dir]]!='#'){
					row+=dx[dir];col+=dy[dir];
				}
			}
			if(com[cur]=='v'){
				if(str[row-dx[dir]][col-dy[dir]]!='#'){
					row-=dx[dir];col-=dy[dir];
				}
			}
			if(com[cur]=='>')dir=(dir+1)%4;
			if(com[cur]=='<')dir=(dir+3)%4;
			cur++;
			ret++;
		}
		if(gr==row&&gc==col){
			break;
		}
		if(vis[row][col][dir][cur]){
			ret=-1;break;
		}
		vis[row][col][dir][cur]=1;
	}
	if(gr!=row||gc!=col)ret=-1;
	printf("%d\n",ret);
}