Babaza Game

#include <bits/stdc++.h>
using namespace std;

#define all(x)  begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x)   (int)(x).size()                                 // signed size: avoids the unsigned .size() wrap bug

using ll  = long long;
using pii = pair<int,int>;
using vi  = vector<int>;

#ifdef LOCAL                                                    // compile with -DLOCAL to enable, silent on the judge
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "] = ", dbg_out(__VA_ARGS__)
template<class T> void dbg_out(T x) { cerr << x << '\n'; }
template<class T, class... R> void dbg_out(T x, R... r) { cerr << x << ", "; dbg_out(r...); }
#else
#define dbg(...)
#endif

int main() {
    cin.tie(0)->sync_with_stdio(0);                             // never mix with scanf/printf after this

    string s, t; cin >> s >> t;
    int n = sz(s);
    if (s == t) { cout << s << "\n"; return 0; }

    string fresh;                                  // 6 letters absent from both words
    for (char c = 'A'; c <= 'Z' && sz(fresh) < 6; c++)
        if (s.find(c) == string::npos && t.find(c) == string::npos) fresh += c;

    for (int k = 1; k <= 4; k++) {
        // all candidate columns for every position
        vector<vector<string>> cols(n);
        for (int i = 0; i < n; i++) {
            string cs = fresh + s[i] + t[i];
            string col(k + 1, '?'); col[0] = s[i]; col[k] = t[i];
            function<void(int)> rec = [&](int j) {
                if (j == k) { cols[i].push_back(col); return; }
                for (char c : cs) { col[j] = c; rec(j + 1); }
            };
            rec(1);
        }
        auto ok = [&](const string &a, const string &b) {
            for (int j = 0; j <= k; j++) if (a[j] == b[j]) return false;                    // valid words
            for (int j = 1; j <= k; j++) if (a[j] != a[j-1] && b[j] != b[j-1]) return false; // no adjacent change
            return true;
        };
        vector<vi> par(n);
        for (int i = 0; i < n; i++) par[i].assign(sz(cols[i]), -2);                            // -2 = unreachable
        for (int a = 0; a < sz(cols[0]); a++) par[0][a] = -1;
        for (int i = 0; i + 1 < n; i++)
            for (int a = 0; a < sz(cols[i]); a++) if (par[i][a] != -2)
                for (int b = 0; b < sz(cols[i+1]); b++)
                    if (par[i+1][b] == -2 && ok(cols[i][a], cols[i+1][b])) par[i+1][b] = a;

        int last = -1;
        for (int b = 0; b < sz(cols[n-1]); b++) if (par[n-1][b] != -2) { last = b; break; }
        if (last < 0) continue;

        vector<string> ch(n);
        for (int i = n - 1; i >= 0; i--) { ch[i] = cols[i][last]; last = par[i][last]; }
        for (int j = 0; j <= k; j++) { string w; for (int i = 0; i < n; i++) w += ch[i][j]; 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