Babaza Game

#include <bits/stdc++.h>


using namespace std;

bool isBabaza(const string &s) {
    for (int i = 1; i < (int)s.size(); i++) {
        if (s[i] == s[i-1]) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string start, target;
    cin >> start >> target;
    int n = start.size();

    queue<string> q;
    unordered_map<string, string> parent;
    q.push(start);
    parent[start] = "";

    while (!q.empty()) {
        string cur = q.front(); q.pop();
        if (cur == target) break;

        vector<int> diff;
        for (int i=0;i<n;i++) if (cur[i]!=target[i]) diff.push_back(i);

        int dsz = diff.size();
        for (int mask=1; mask < (1<<dsz); mask++) {
            bool ok=true;
            for (int j=1;j<dsz;j++) {
                if ((mask&(1<<j)) && (mask&(1<<(j-1)))) {
                    if (diff[j]==diff[j-1]+1) { ok=false; break; }
                }
            }
            if (!ok) continue;
            string nxt=cur;
            for (int j=0;j<dsz;j++) if (mask&(1<<j)) nxt[diff[j]]=target[diff[j]];
            if (!isBabaza(nxt)) continue;
            if (!parent.count(nxt)) {
                parent[nxt]=cur;
                q.push(nxt);
            }
        }
        for (int pos=0;pos<n;pos++) if (cur[pos]!=target[pos]) {
            for (char c='A';c<='Z';c++) {
                if (c==cur[pos] || c==target[pos]) continue;
                string nxt=cur;
                nxt[pos]=c;
                if (!isBabaza(nxt)) continue;
                if (!parent.count(nxt)) {
                    parent[nxt]=cur;
                    q.push(nxt);
                }
            }
        }
    }
    vector<string> path;
    string cur=target;
    while (cur!="") {
        path.push_back(cur);
        cur=parent[cur];
    }
    reverse(path.begin(), path.end());

    for (auto &w : path) cout << w << "\n";
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED