Auto comment: topic has been updated by detective12 (previous revision, new revision, compare).

I'm not sure if this will tle or not but ig you can try

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")

using namespace std;

using ll = long long;

int bfs(vector<char>& s, int n) {
    queue<pair<vector<char>, int>> q;
    unordered_set<string> visited;
    string initial_state(s.begin(), s.end()); // Convert to string for the visited set
    q.push({s, 0});
    visited.insert(initial_state);

    // Create the goal prefix in a vector form
    vector<char> goal_prefix(n);
    fill(goal_prefix.begin(), goal_prefix.begin() + n / 2 - 1, 'A');
    fill(goal_prefix.begin() + n / 2 - 1, goal_prefix.end(), 'B');

    while (!q.empty()) {
        auto [state, moves] = q.front();
        q.pop();
        
        int pos1 = find(state.begin(), state.end(), 'O') - state.begin(); // Position of first 'O'
        int pos2 = pos1 + 1; // Second 'O' position

        // Check if we've reached the goal state
        bool reachedH = false;
        bool valid = true;
        for (char c : state) {
            if (reachedH) {
                if (c == 'A') valid = false;
            } else if (c == 'B') {
                reachedH = true;
            }
        }
        if (valid) return moves;

        // Generate all possible next states
        for (int i = 0; i < n - 1; ++i) {
            if (!(i - 1 == pos1 || i == pos1 || i + 1 == pos1)) {
                vector<char> next_state = state; // Create a copy for the next state
                next_state[pos1] = state[i];
                next_state[pos2] = state[i + 1];
                next_state[i] = 'O';
                next_state[i + 1] = 'O';

                // Convert next_state to string for visited check
                string next_state_str(next_state.begin(), next_state.end());
                if (visited.find(next_state_str) == visited.end()) {
                    visited.insert(next_state_str);
                    q.push({next_state, moves + 1});
                }
            }
        }
    }
    return -1; // If no solution was found
}

int main() {
    int t; 
    cin >> t;
    for (int _ = 0; _ < t; ++_) {
        int n; 
        cin >> n;
        string input; 
        cin >> input;

        // Convert the input string to a vector<char>
        vector<char> s(input.begin(), input.end());

        int result = bfs(s, n);
        if (result == -1) {
            cout << "IMPOSSIBLE" << endl;
        } else {
            cout << result << endl;
        }
    }
    return 0;
}