読者です 読者をやめる 読者になる 読者になる

ichirin2501's diary

いっちりーん。

問題 D - 停止問題

http://atcoder.jp/problem/detail/28
245(76)分で正解


やるだけー、と思って、何を思ったのかqueueで書き出す。
途中で、サイズが小さいので再帰でいいや、ということで再帰に変える。
基本はシミュレーションでおk、ただし、ループする可能性もあるので
ループ検出のために状態を保存しておく必要がある
状態の情報は 座標とメモリの値と現在の処理の向き の3種類です
現在の処理の向きの情報をすっかり忘れてて2WA

const int dx[] = {0,1,0,-1}; //up,right,down,left;
const int dy[] = {-1,0,1,0};
bool check[22][22][22][4]; //[mem][y][x][dir]
int r,c;
char vs[32][32];

bool solve(int mem, int x, int y, int dir){
  if( check[mem][y][x][dir] ) return false;
  check[mem][y][x][dir] = true;

  bool f = false;

  if( vs[y][x]=='<' ){
    dir = 3;
  }else if( vs[y][x]=='>' ){
    dir = 1;
  }else if( vs[y][x]=='^' ){
    dir = 0;
  }else if( vs[y][x]=='v' ){
    dir = 2;
  }else if( vs[y][x]=='_' ){
    dir = (mem==0 ? 1 : 3);
  }else if( vs[y][x]=='|' ){
    dir = (mem==0 ? 2 : 0);
  }else if( vs[y][x]=='?' ){ // 
    f = true;
  }else if( vs[y][x]=='.' ){ // nop
    ;
  }else if( vs[y][x]=='@' ){ // end
    return true;
  }else if( '0'<=vs[y][x] && vs[y][x]<='9' ){ //mov
    mem = vs[y][x]-'0';
  }else if( vs[y][x]=='+' ){ // inc
    mem++;
    if(mem>15)mem=0;
  }else if( vs[y][x]=='-' ){ // dec
    mem--;
    if(mem<0)mem=15;
  }

  if( !f ){
    int tx = x + dx[dir];
    int ty = y + dy[dir];
    if( tx<0 ) tx=c-1;
    if( tx>=c ) tx=0;
    if( ty<0 ) ty=r-1;
    if( ty>=r ) ty=0;
    return solve(mem,tx,ty,dir);
  }else{ // ? ver
    rep(k,4){
      int tx = x + dx[k];
      int ty = y + dy[k];
      if( tx<0 ) tx=c-1;
      if( tx>=c ) tx=0;
      if( ty<0 ) ty=r-1;
      if( ty>=r ) ty=0;
      if( solve(mem,tx,ty,k) ) return true;
    }
  }
  return false;
}

int main(){
  while(cin>>r>>c){
    rep(i,22)rep(j,22)rep(k,22)rep(l,4)check[i][j][k][l]=false;
    rep(i,r){
      cin>>vs[i];
    }
    puts(solve(0,0,0,1) ? "YES" : "NO");
  }
  return 0;
}