[1824][D4] 혁진이의 프로그램 검증

풀이

1. check 배열은 x, y에서 memory를 가지고 direct방향에 온 적이 있는지를 나타낸다. 같은 조건으로 같은 장소를 방문했다면 무한 루프이다.
2. map과 pair를 따로 저장해서 특정 위치에 올 때마다 pair를 갱신한다면, 두 바퀴가 주기인 무한 루프를 잡지 못한다. 1번처럼 해야한다.
3. check 배열에서 mem은 0~15이므로 크기가 16이 들어가야 한다.

4. ret = ret

   dfs(nx, ny, mem, k);는 한 번이라도 true가 나온 적이 있으면 true를 return 한다는 뜻이다.

코드

#include <cstdio>
#include <cstring>
#define RIGHT 0
#define LEFT 1
#define DOWN 2
#define UP 3
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };

char map[20][20];
bool check[20][20][16][4];
int R, C;

bool dfs(int x, int y, int mem, int dir) {
	bool ret = false;
	if ('0' <= map[x][y] && map[x][y] <= '9') mem = map[x][y] - '0';
	else if (map[x][y] == '<' || (map[x][y] == '_' && mem != 0)) dir = LEFT;
	else if (map[x][y] == '>' || (map[x][y] == '_' && mem == 0)) dir = RIGHT;
	else if (map[x][y] == '^' || (map[x][y] == '|' && mem != 0)) dir = UP;
	else if (map[x][y] == 'v' || (map[x][y] == '|' && mem == 0)) dir = DOWN;
	else if (map[x][y] == '@') return true;
	else if (map[x][y] == '+') mem = (mem + 1) % 16;
	else if (map[x][y] == '-') mem = (mem - 1 + 16) % 16;

	if (check[x][y][mem][dir]) return false;
	else check[x][y][mem][dir] = true;

	int nx = x + dx[dir];
	int ny = y + dy[dir];
	if (nx == -1) nx = R - 1;
	else if (nx == R) nx = 0;
	if (ny == -1) ny = C - 1;
	else if (ny == C) ny = 0;

	if (map[x][y] == '?') {
		for (int k = 0; k < 4; k++) {
			nx = x + dx[k];
			ny = y + dy[k];
			if (nx == -1) nx = R - 1;
			else if (nx == R) nx = 0;
			if (ny == -1) ny = C - 1;
			else if (ny == C) ny = 0;
			ret = ret || dfs(nx, ny, mem, k);
		}
		return ret;
	}
	else {
		ret = ret || dfs(nx, ny, mem, dir);
		return ret;
	}
}

int main(void) {
	int tcase = 0;
	scanf("%d", &tcase);
	for (int tc = 1; tc <= tcase; tc++) {
		memset(map, ' ', sizeof(map));
		memset(check, false, sizeof(check));
		scanf("%d %d", &R, &C);
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				scanf(" %c", &map[i][j]);
			}
		}
		printf("#%d %s\n", tc, dfs(0, 0, 0, RIGHT) ? "YES" : "NO");
		
	}
	
	return 0;
}