SW expert academy 1824 혁진이의 프로그램 검증

기본적인 풀이는 DFS이다.

DP[i][j][memory][direct]는 

"i, j의 위치에서 memory의 값을 메모리에 저장해놨을 때, direct로 프로그램이 진행되고 있는 상황에서의 프로그램이 끝날 수 있는 지의 여부"

이다.

그 결과값이 1이면 끝날 수 있고, 2이면 끝날 수 없음을 의미한다.

혁진이의 프로그램이 무한루프가 돈다는 것은, 같은 memory와 direct의 상황에서 같은 i,j를 방문했다는 것으로 체크하면 된다.

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string.h>
#include <utility>
#include <set>
#include <queue>
#include <stack>
#include <functional>
#include <math.h>
#include <string>
#include <sstream>

using namespace std;


int T;
int R, C;

char arr[21][21];

int memo[21][21][16][4];
int tt[4][3] = { {0,-1, 0}, {-1, 0, 1} , {0, 1, 2}, {1, 0, 3} };

int dfs(int nowi, int nowj, int memory, int direct) { // 0, 1, 2, 3 왼 위 우 하
	int& m = memo[nowi][nowj][memory][direct];

	if (m == 1 || m == 2) return m;
	if (m == -1) {
		m = 2;
		return 2;
	}
	m = -1;

	if (arr[nowi][nowj] <= '9' && arr[nowi][nowj] >= '0') {
		memory = arr[nowi][nowj] - '0';

		int nexti = nowi + tt[direct][0];
		int nextj = nowj + tt[direct][1];

		if (nexti >= R) nexti = 0;
		else if (nexti < 0) nexti = R - 1;

		if (nextj >= C) nextj = 0;
		else if (nextj < 0) nextj = C - 1;

		m = dfs(nexti, nextj, memory, direct);
	}
	else {
		int nexti, nextj;
		int nextDirect = 0;
		bool flag = false;
		switch (arr[nowi][nowj]) {
		case '?':
			for (auto t : tt) {
				nexti = nowi + t[0];
				nextj = nowj + t[1];

				if (nexti >= R) nexti = 0;
				else if (nexti < 0) nexti = R - 1;

				if (nextj >= C) nextj = 0;
				else if (nextj < 0) nextj = C - 1;

				int& nextm = memo[nexti][nextj][memory][t[2]];
				if (dfs(nexti, nextj, memory, t[2]) == 1) {
					m = 1;
					flag = true;
					break;
				}
			}
			if (flag == false) {
				m = 2;
			}
			break;
		case '@':
			m = 1;
			break;
		case '<':
			nextj = nowj - 1;
			if (nextj < 0) nextj = C - 1;
			m = dfs(nowi, nextj, memory, 0);
			break;
		case '^':
			nexti = nowi - 1;
			if (nexti < 0) nexti = R - 1;
			m = dfs(nexti, nowj, memory, 1);
			break;
		case '>':
			nextj = nowj + 1;
			if (nextj >= C) nextj = 0;
			m = dfs(nowi, nextj, memory, 2);
			break;
		case 'v':
			nexti = nowi + 1;
			if (nexti >= R) nexti = 0;
			m = dfs(nexti, nowj, memory, 3);
			break;
		case '|':
			if (memory == 0) {
				nextDirect = 3;
				nexti = nowi + 1;
				if (nexti >= R) nexti = 0;
			}
			else {
				nextDirect = 1;
				nexti = nowi - 1;
				if (nexti < 0) nexti = R - 1;
			}
			m = dfs(nexti, nowj, memory, nextDirect);
			break;
		case '_':
			if (memory == 0) {
				nextDirect = 2;
				nextj = nowj + 1;
				if (nextj >= C) nextj = 0;
			}
			else {
				nextDirect = 0;
				nextj = nowj - 1;
				if (nextj < 0) nextj = C - 1;
			}
			m = dfs(nowi, nextj, memory, nextDirect);
			break;
		case '+':
			memory++;
			if (memory >= 16) memory = 0;

			nexti = nowi + tt[direct][0];
			nextj = nowj + tt[direct][1];

			if (nexti >= R) nexti = 0;
			else if (nexti < 0) nexti = R - 1;

			if (nextj >= C) nextj = 0;
			else if (nextj < 0) nextj = C - 1;

			m = dfs(nexti, nextj, memory, direct);
			break;
		case '-':
			memory--;
			if (memory < 0) memory = 15;

			nexti = nowi + tt[direct][0];
			nextj = nowj + tt[direct][1];

			if (nexti >= R) nexti = 0;
			else if (nexti < 0) nexti = R - 1;

			if (nextj >= C) nextj = 0;
			else if (nextj < 0) nextj = C - 1;

			m = dfs(nexti, nextj, memory, direct);
			break;
		case '.':
			nexti = nowi + tt[direct][0];
			nextj = nowj + tt[direct][1];

			if (nexti >= R) nexti = 0;
			else if (nexti < 0) nexti = R - 1;

			if (nextj >= C) nextj = 0;
			else if (nextj < 0) nextj = C - 1;

			m = dfs(nexti, nextj, memory, direct);
			break;

		}
	}

	return m;
}

int main() {
	scanf("%d", &T);

	for (int tc = 1; tc <= T; tc++) {

		for (int i = 0; i < 21; i++) {
			for (int j = 0; j < 21; j++) {
				arr[i][j] = 'A';
				for (int a1 = 0; a1 < 16; a1++) {
					for (int a2 = 0; a2 < 4; a2++) {
						memo[i][j][a1][a2] = 0;
					}
				}
			}
		}


		scanf("%d %d", &R, &C);

		string tempstr;

		bool noalpha = true;

		for (int i = 0; i < R; i++) {

			cin >> tempstr;

			for (int j = 0; j < C; j++) {
				arr[i][j] = tempstr[j];
				if (arr[i][j] == '@') {
					noalpha = false;
				}
			}
		}
		int result = -1;
		if (!noalpha) result = dfs(0, 0, 0, 2);


		string res = (result == 1) ? "YES" : "NO";

		cout << "#" << tc << " " << res << endl;
	}

	return 0;
}