[SWEA] 1824. 혁진이의 프로그램 검증 C++

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4yLUiKDUoDFAUx

SW Expert Academy

 

4중 벡터는 또 처음 써봅니다...

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct Node {
	int y;
	int x;
	int d;
	int mem;
};

int R, C;
vector<vector<char>> map;
vector<vector<vector<vector<int>>>> visited;
int direct[4][2] = {
	0, -1,
	0, 1,
	-1, 0,
	1, 0,
};

int main() {
	int T;
	cin >> T;
	for (int tc = 1; tc <= T; tc++) {
		int mem = 0;
		map.clear();
		visited.clear();

		cin >> R >> C;
		map.assign(R, vector<char>(C, ' '));

		for (int i = 0; i < R; i++) {
			string tmp;
			cin >> tmp;
			for (int j = 0; j < C; j++) {
				map[i][j] = tmp[j];
			}
		}
		
		int i = 0, j = 0, d = 0;
		visited.assign(R, vector<vector<vector<int>>>(C, vector<vector<int>>(4, vector<int>(16, 0))));
		queue <Node> q;
		visited[0][0][1][mem] = 1;
		q.push({ 0, 0, 1, mem });
		bool isDone = false;
		while (!q.empty()) {
			Node now = q.front();
			i = now.y;
			j = now.x;
			d = now.d;
			mem = now.mem;
			q.pop();

			
			if (map[i][j] == '@') {
				isDone = true;
				break;
			}

			if (map[i][j] == '<') {
				d = 0;
			}
			else if (map[i][j] == '>') {
				d = 1;
			}
			else if (map[i][j] == '^') {
				d = 2;
			}
			else if (map[i][j] == 'v') {
				d = 3;
			}
			else if (map[i][j] == '_') {
				if (mem == 0) d = 1;
				else d = 0;
			}
			else if (map[i][j] == '|') {
				if (mem == 0) d = 3;
				else d = 2;
			}
			else if (map[i][j] >= '0' && map[i][j] <= '9') {
				mem = map[i][j] - '0';
			}
			else if (map[i][j] == '+') {
				if (mem >= 15) mem = 0;
				else mem++;
			}
			else if (map[i][j] == '-') {
				if (mem <= 0) mem = 15;
				else mem--;
			}
			else if (map[i][j] == '?') {
				// 이동 방향을 상하좌우 중 하나로 무작위로 바꾼다
				for (int k = 0; k < 4; k++) {
					
					int dy = (i + direct[k][0] + R) % R;
					int dx = (j + direct[k][1] + C) % C;

					if (visited[dy][dx][k][mem]) continue;
					visited[dy][dx][k][mem] = 1;

					q.push({ dy, dx, k, mem });
				}
				continue;
			}

			int dy = (i + direct[d][0] + R) % R;
			int dx = (j + direct[d][1] + C) % C;

			if (visited[dy][dx][d][mem]) continue;
			visited[dy][dx][d][mem] = 1;
			
			q.push({ dy, dx, d, mem });
		}

		cout << "#" << tc << " ";
		if (isDone) cout << "YES\n";
		else cout << "NO\n";
	}

	return 0;
}