SWEA 1824 혁진이의 프로그램 인증

설계:

결국에는 src에서 dst로 갈 수 있는지 dfs(vst 추가 차원 필요)

 

코드:

처음에는 visited를 좌표, 메모리 기준으로만 처리했으나 3개의 TC가 통과되지 않아

방향을 추가하여 AC

#include <iostream>
#define f(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
int R, C;
char prg[20][20];
int vst[20][20][18][4], v;
int rot[4], rots;
int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };
int ad[16], sb[16];
void edge(int &r, int &c) {
	if (r == -1)
		r = R - 1;
	else if (r == R)
		r = 0;
	if (c == -1)
		c = C - 1;
	else if (c == C)
		c = 0;
}
bool dfs(int r, int c, int d, int m) {
	vst[r][c][m][d] = v;
	if (prg[r][c] == '@')
		return 1;

	if ('0' <= prg[r][c] && prg[r][c] <= '9')
		m = prg[r][c] - '0';
	else
		switch (prg[r][c]) {
		case '<': d = 3; break;
		case '>': d = 1; break;
		case '^': d = 0; break;
		case 'v': d = 2; break;
		case '_': d = (!m) ? 1 : 3; break;
		case '|': d = (!m) ? 2 : 0; break;
		case '+': m = ad[m]; break;
		case '-': m = sb[m]; break;
		}
	
	int nr = r + dr[d], nc = c + dc[d];
	edge(nr, nc);
	if (vst[nr][nc][m][d] == v) goto out;
	if (dfs(nr, nc, d, m)) return 1;

out:
	if(prg[r][c] == '?')
		f(nd, 4)
			if (nd != d) {
				int nr = r + dr[nd], nc = c + dc[nd];
				edge(nr, nc);
				if (vst[nr][nc][m][nd] == v) continue;
				if (dfs(nr, nc, nd, m)) return 1;
			}
	return 0;
}
int main() {
	f(a, 16) ad[a] = a + 1;
	ad[15] = 0;
	f(s, 16) sb[s] = s - 1;
	sb[0] = 15;

	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T; cin >> T;
	for (int tc = 1; tc <= T; ++tc) {
		cin >> R >> C;
		f(r, R) f(c, C) cin >> prg[r][c];
		++v;
		cout << '#' << tc << ' ';
		cout << ((dfs(0, 0, 1, 0)) ? "YES" : "NO") << '\n';	
	}
	return 0;
}