• 처음에 문제를 잘 안 읽고 코딩부터 시작했다 -> 그러지 말자
    • simulation인줄 알고 그렇게 구현을 했다가 수정을 해야만 했다.
  • row, col, 그리고 방향만 가지고 재방문 여부를 판단하도록 구현했다.
    • visited[row][col][dir]
    • 이 또한 잘못된 방법이다.
  • 이후에 row, col, 방향(4개), 메모리 값(10개)으로 재방문 여부를 판단했다.
    • visited[row][col][dir][memory]


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125



#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <set>

using namespace std;

#define MAX_N 22

int R, C;
bool visited[MAX_N][MAX_N][4][16];
string board[MAX_N];
int dx[4] = { 0, -1, 0, 1};
int dy[4] = {-1,  0, 1, 0};

void init() {
	memset(visited, 0, sizeof(visited));

	cin >> R >> C;
	for (int i = 0; i < R; i++)
		cin >> board[i];
}

struct Node {
	int r, c, d, s;
	Node(int _r, int _c, int _d, int _s) {
		r = _r; c = _c; d = _d; s = _s; 
	}
};

void solution() {
	queue<Node> q;
	Node startNod(0, 0, 2, 0);

	q.push(startNod);
	visited[0][0][2][0] = true;

	int cnt = 0;
	while (!q.empty()) {
		for (int qs = 0, qSize = q.size(); qs < qSize; qs++) {
			int r = q.front().r;
			int c = q.front().c;
			int dir = q.front().d;
			int s = q.front().s;
			q.pop();

			bool isQuestionMark = false;
			switch(board[r][c]) {
				case '<':
					dir = 0;
					break;
				case '^':
					dir = 1;
					break;
				case '>':
					dir = 2;
					break;
				case 'v':
					dir = 3;
					break;
				case '_':
					if (s == 0) dir = 2;
					else dir = 0;
					break;
				case '|':
					if (s == 0) dir = 3;
					else dir = 1;
					break;
				case '?':
					isQuestionMark = true;
					break;
				case '.':
					break;
				case '@':
					return true;
				case '+':
					s = (s+1) % 16;
					break;
				case '-':
					s = (s == 0 ? 15: s - 1);
					break;
				default:
					s = board[r][c] - '0';
					break;
			}
			if (isQuestionMark) {
				for (int i = 0; i < 4; i++) {
					int nr = (r + dx[i] + R) % R;
					int nc = (c + dy[i] + C) % C;
					if (visited[nr][nc][i][s]) continue;

					visited[nr][nc][i][s] = true;
					Node nod(nr, nc, i, s);
					q.push(nod);
				}
			}
			else {
				int nr = (r + dx[dir] + R) % R;
				int nc = (c + dy[dir] + C) % C;
				if (visited[nr][nc][dir][s]) continue;

				visited[nr][nc][dir][s] = true;
				Node nod(nr, nc, dir, s);
				q.push(nod);
			}
		}
		cnt++;
	}
	return false;
}

int main() {
	int testcase;
	scanf("%d", &testcase);
	for (tc = 1; tc <= testcase; tc++) {
		init();
		cout << "#" << tc << " " << (solution()? "YES" : "NO") << endl;
	}
}