AOJ 2643 AI
問題
方針
お決まりの構文解析をする。 具体的には、それぞれの規則 (プログラム、文if、while、動作文、条件文) を読み込むための関数を書き、 その中で BNF 通りにお互いを呼び出し合う。 やることが多いのでバグらないように注意する。ファースト集合 (各規則がどの文字から始まりうるか) を意識して書くとバグりにくいしデバッグしやすいと思う。
実装
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
// N E S W
int di[] = {-1, 0, 1, 0};
int dj[] = {0, 1, 0, -1};
int h,w;
char g[60][60];
char op[1010];
char vis[60][60][4][1010];
char vis_while[60][60][4][1010];
int dir;
int ci, cj;
char *Prog(char *);
pair<char*,bool> Cond(char *);
pair<char*,bool> Cond(char *p){
bool inv = false;
if(*p == '~'){
inv = true;
++p;
}
bool res = false ||
(*p=='N' && dir == 0) ||
(*p=='E' && dir == 1) ||
(*p=='S' && dir == 2) ||
(*p=='W' && dir == 3) ||
(*p=='C' && g[ci+di[dir]][cj+dj[dir]] == '#') ||
(*p=='T');
res ^= inv;
++p;
return make_pair(p,res);
}
char *If(char *p){
++p;
bool cond;
tie(p,cond) = Cond(p);
if(cond){
p = Prog(p);
++p;
return p;
} else {
int d = 1;
while(d != 0){
if(*p == '[') ++d;
else if(*p == ']') --d;
++p;
}
return p;
}
}
char *While(char *p){
++p;
char *cond_begin = p;
while(1){
if(vis_while[ci][cj][dir][p-op]) throw -1;
vis_while[ci][cj][dir][p-op] = true;
bool cond;
tie(p,cond) = Cond(p);
if(cond){
p = Prog(p);
p = cond_begin;
} else {
int d = 1;
while(d != 0){
if(*p == '{') ++d;
else if(*p == '}') --d;
++p;
}
return p;
}
}
}
int cnt;
char *Move(char *p){
if(vis[ci][cj][dir][p-op]) throw -1;
vis[ci][cj][dir][p-op] = true;
++cnt;
if(*p == '>') dir = (dir+1) & 3;
if(*p == '<') dir = (dir-1) & 3;
if(*p == 'v'){
int ni = ci + di[(dir+2) & 3];
int nj = cj + dj[(dir+2) & 3];
if(g[ni][nj] != '#'){
ci = ni; cj = nj;
}
}
if(*p == '^'){
int ni = ci + di[dir];
int nj = cj + dj[dir];
if(g[ni][nj] != '#'){
ci = ni; cj = nj;
}
}
if(g[ci][cj] == 'g') throw cnt;
++p;
return p;
}
char *Statement(char *p){
if(*p == '[') p = If(p);
else if(*p == '{') p = While(p);
else p = Move(p);
return p;
}
char *Prog(char *p){
while(*p == '[' || *p == '{' || *p == '^' || *p == 'v' || *p == '<' || *p == '>'){
p = Statement(p);
}
return p;
}
int main(){
while(cin >> h >> w){
memset(vis, 0, sizeof vis);
memset(vis_while, 0, sizeof vis_while);
cnt = 0;
dir = 0;
rep(i,h) cin >> g[i];
rep(i,h) rep(j,w) if(g[i][j] == 's') ci = i, cj = j;
cin >> op;
int ans = -1;
try {
Prog(op);
} catch(int r){
ans = r;
}
cout << ans << endl;
}
}