UTPC2011 D: 停止問題
解法
座標、メモリの値、向きの組を状態としてflood fill。余計なローカル変数が無ければ再帰で書いても大丈夫。Gの盤面上での振る舞いとdy[]の中の値を書き間違えていてWA連発。
#include <cstdio> using namespace std; int W, H; char board[22][22]; int dy[] = {-1,1,0,0}; int dx[] = {0,0,1,-1}; bool visited[22][22][22][4]; bool dfs(int y, int x, int a, int d){ if(y==-1) y=H-1; if(y==H) y = 0; if(x==-1) x=W-1; if(x==W) x = 0; if(visited[y][x][a][d]) return false; visited[y][x][a][d] = true; if(board[y][x]=='@') return true; if(board[y][x]=='<'){d = 3; return dfs(y+dy[d],x+dx[d],a,d); } if(board[y][x]=='>'){d = 2; return dfs(y+dy[d],x+dx[d],a,d); } if(board[y][x]=='^'){d = 0; return dfs(y+dy[d],x+dx[d],a,d); } if(board[y][x]=='v'){d = 1; return dfs(y+dy[d],x+dx[d],a,d); } if(board[y][x]=='_'){d = (a?3:2); return dfs(y+dy[d],x+dx[d],a,d); } if(board[y][x]=='|'){d = (a?0:1); return dfs(y+dy[d],x+dx[d],a,d); } if(board[y][x]=='.' || board[y][x]=='G'){return dfs(y+dy[d],x+dx[d],a,d); } if(board[y][x]=='+'){a = ((a+1)&15); return dfs(y+dy[d],x+dx[d],a,d); } if(board[y][x]=='-'){a = ((a-1)&15); return dfs(y+dy[d],x+dx[d],a,d); } if(board[y][x]=='?'){ for(d=0; d<4; d++){ if(dfs(y+dy[d],x+dx[d],a,d)) return true; } return false; } a = (board[y][x]&15); return dfs(y+dy[d], x+dx[d], a, d); } int main(){ scanf("%d%d ",&H,&W); for(int i=0; i<H; i++){ scanf("%s ",board[i]); } puts(dfs(0,0,0,2)?"YES":"NO"); return 0; }