AOJ 2643 AI

2016/04/22 (Fri) AOJ 構文解析

問題

問題文

方針

お決まりの構文解析をする。 具体的には、それぞれの規則 (プログラム、文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;
    }
}