소프티어

#include <algorithm>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

using namespace std;

#define PER_INTERSECTION_SIGNALS 4
#define SIG_TYPES 12
#define MAX_SIGS  4

typedef pair<int, int> position;

const position NO_SIG = { 0, 0 };
const position LEFT = { -1, 0 };
const position UP = { 0, -1 };
const position RIGHT = { 1, 0 };
const position DOWN = { 0, 1 };

const position SIG_DIRS[MAX_SIGS] = {
    RIGHT,
    UP,
    LEFT,
    DOWN
};

const position SIGS[SIG_TYPES][MAX_SIGS] = {
    { NO_SIG, RIGHT, UP, DOWN },
    { NO_SIG, LEFT, RIGHT, UP },
    { NO_SIG, LEFT, UP, DOWN },
    { NO_SIG, LEFT, RIGHT, DOWN },
    { NO_SIG, NO_SIG, RIGHT, UP },
    { NO_SIG, NO_SIG, LEFT, UP },
    { NO_SIG, NO_SIG, LEFT, DOWN },
    { NO_SIG, NO_SIG, RIGHT, DOWN },
    { NO_SIG, NO_SIG, RIGHT, DOWN },
    { NO_SIG, NO_SIG, RIGHT, UP },
    { NO_SIG, NO_SIG, LEFT, UP },
    { NO_SIG, NO_SIG, LEFT, DOWN }
};

int map_size, simulation_time;
vector<vector<bool>> visited;
vector<vector<int>> sig_seqs;

bool is_valid_position(position target)
{
    if(target.first < 0 || target.second < 0 || target.first >= map_size || target.second >= map_size)
        return false;

    return !visited[target.first][target.second];
}

int simulate()
{
    int passed_intersections = 0;
    queue<pair<pair<position, position>, int>> positions;

    positions.push({{ { 0, 1 }, UP },  0});
    
    while(!positions.empty())
    {
        auto ongoing = positions.front();
        positions.pop();

        auto current = ongoing.first.first;
        auto offset = ongoing.first.second;
        int t = ongoing.second;

        pair<int, int> next = { current.first + offset.first, current.second + offset.second };

        if(!is_valid_position(next))
            continue;

        visited[next.first][next.second] = true;
        ++passed_intersections;

        if(t + 1 > simulation_time)
            continue;

        int sig_seq_idx = next.second * map_size + next.first;
        int current_sig = sig_seqs[sig_seq_idx][t % PER_INTERSECTION_SIGNALS] - 1;
        auto next_dir = SIG_DIRS[current_sig % PER_INTERSECTION_SIGNALS];

        if(offset != next_dir)
            continue;

        for(const auto& sig: SIGS[current_sig])
        {
            if(sig == NO_SIG)
                continue;

            position new_next = { next.first + sig.first, next.second + sig.second };

            if(!is_valid_position(new_next))
                continue;

            positions.push({{ next, sig }, t + 1});
        }
    }
    
    return passed_intersections;
}

int main(int argc, char** argv)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> map_size >> simulation_time;
    visited.resize(map_size, vector<bool>(map_size));
    
    for(int i = 0; i < map_size * map_size; ++i)
    {
        sig_seqs.push_back(vector<int>(PER_INTERSECTION_SIGNALS));

        for(int j = 0; j < PER_INTERSECTION_SIGNALS; ++j)
            cin >> sig_seqs[i][j];
    }

    cout << simulate();
    return 0;
}

Subtask 1은 정답인데 2에서 절반 가량이 오답으로 나옵니다. 참고할 만한 반례가 있을까요?