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