1824. 혁진이의 프로그램 검증

bfs 문제다.

visit배열은 c[x][y][w][mem]으로 체크해주면 된다.

'?'를 만나면 현재의 mem을 가지고 4방향으로 진행했을 때의 좌표를 가지고 visit배열을 참조해서 안간쪽으로만 queue에 넣어주면 된다.

#include <iostream>
#include <queue>
#include <memory.h>
using namespace std;
 
struct p {
    int x, y, w, mem;
};
 
int t, tc, n, m;
int dx[] = { -1,0,1,0 }, dy[] = { 0,1,0,-1 }, c[21][21][4][16];
char a[21][21];
queue<p> q;
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> t;
    for (tc = 1; tc <= t; ++tc) {
        cin >> n >> m;
        bool able = false;
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            if (!able) {
                for (int j = 0; j < m; ++j) 
                    if (a[i][j] == '@') able = true;
            }
        }
        if (able) q.push({ 0,0,1,0 });
        c[0][0][1][0] = tc;
        int f = 0;
        while (q.size()) {
            int x = q.front().x;
            int y = q.front().y;
            int w = q.front().w;
            int mem = q.front().mem;
            q.pop();
            if (a[x][y] == '<') w = 3;
            else if (a[x][y] == '>') w = 1;
            else if (a[x][y] == '^') w = 0;
            else if (a[x][y] == 'v') w = 2;
            else if (a[x][y] == '_') w = mem == 0 ? 1 : 3;
            else if (a[x][y] == '|') w = mem == 0 ? 2 : 0;
            else if (a[x][y] == '?') {
                for (int i = 0; i < 4; ++i) {
                    int nx = (x + dx[i] + n) % n;
                    int ny = (y + dy[i] + m) % m;
                    if (c[nx][ny][i][mem] == tc) continue;
                    c[nx][ny][i][mem] = tc;
                    q.push({ nx,ny,i,mem });
                }
                continue;
            }
            else if (a[x][y] == '@') {
                f = 1;
                while (q.size()) q.pop();
                break;
            }
            else if (a[x][y] >= '0' && a[x][y] <= '9') mem = a[x][y] - '0';
            else if (a[x][y] == '+') mem = (mem + 1) % 16;
            else if (a[x][y] == '-') mem = (mem + 15) % 16;
 
            x = (x + dx[w] + n) % n;
            y = (y + dy[w] + m) % m;
            if (c[x][y][w][mem] == tc) continue;
            c[x][y][w][mem] = tc;
            q.push({ x,y,w,mem });
        }
        
        cout << '#' << tc << ' ' << (f ? "YES" : "NO") << '\n';
    }
    return 0;
}