#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <tuple>
using namespace std;
typedef tuple<int, int, int, int> state;
const int dy[] = { -1, +1, 0, 0 };
const int dx[] = { 0, 0, -1, +1 };
int R; // 세로 크기
int C; // 가로 크기
vector<string> map; // 격자
int input()
{
cin >> R >> C;
map.assign(R, "");
for (int r = 0; r < R; ++r) cin >> map[r];
int valid = 0;
for (const auto& s : map)
{
for (const auto& c : s)
{
if (!valid && c == '@') valid = 1;
}
}
if (valid) return 0;
else return -1;
}
string solve()
{
string answer = "NO";
if (input() < 0)
{
answer = "NO";
}
else
{
state init = make_tuple(0, 0, 3, 0); // 좌상단 위치, 오른쪽 이동방향, 메모리 0
queue<state> q; q.emplace(init); // 큐에 삽입
vector<vector<vector<vector<int> > > > visited(R, vector<vector<vector<int> > >(C, vector<vector<int> >(4, vector<int>(16, 0))));
visited[0][0][3][0] = 1; // 방문처리
while (!q.empty())
{
int cy, cx, dir, mem;
tie(cy, cx, dir, mem) = q.front(); q.pop();
char c = map[cy][cx];
if (c == '<') dir = 2;
else if (c == '>') dir = 3;
else if (c == '^') dir = 0;
else if (c == 'v') dir = 1;
else if (c == '_') mem == 0 ? dir = 3 : dir = 2;
else if (c == '|') mem == 0 ? dir = 1 : dir = 0;
else if ('0' <= c && c <= '9') mem = c - '0';
else if (c == '+') mem == 15 ? mem = 0 : mem += 1;
else if (c == '-') mem == 0 ? mem = 15 : mem -= 1;
else if (c == '@')
{
answer = "YES";
break;
}
if (c == '?')
{
int cnt = 0;
for (int d = 0; d < 4; ++d)
{
dir = d;
int ny = (cy + dy[dir] + R) % R;
int nx = (cx + dx[dir] + C) % C;
if (visited[ny][nx][dir][mem])
{
continue;
}
else
{
visited[ny][nx][dir][mem] = 1;
q.emplace(ny, nx, dir, mem);
cnt += 1;
}
}
if (cnt == 0)
{
continue;
}
}
else
{
int ny = (cy + dy[dir] + R) % R;
int nx = (cx + dx[dir] + C) % C;
if (visited[ny][nx][dir][mem])
{
continue;
break;
}
else
{
visited[ny][nx][dir][mem] = 1;
q.emplace(ny, nx, dir, mem);
}
}
}
}
return answer;
}
int main()
{
//freopen("sample_input_swea_1824.txt", "r", stdin);
ios_base::sync_with_stdio(0);
cin.tie(0);
int TC; cin >> TC;
for (int tc = 1; tc <= TC; ++tc)
{
cout << "#" << tc << " " << solve() << endl;
}
return 0;
}
핵심은 기본 BFS 구조에 (1) 순환을 어떻게 잡아낼 것인지, (2) ? 문자의 경우 어떻게 처리할 것인지 이다.
(1) 순환 잡아내기
순환의 경우 같은 위치에, 같은 방향, 같은 메모리 값으로 되돌아 왔을 경우 순환이라고 판단할 수 있으므로 4차원 방문배열을 사용하도록 한다.(2) ? 문자 처리하기
? 문자의 경우 랜덤으로 4방향 중 한 곳으로 간다고 했으므로 4방향 탐색 반복문을 짜도록 한다. 이때 바로 방문로직과 큐 삽입 로직을 수행해야 하므로 다른 케이스와 구분하여 구현하도록 한다.