問題 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; }