The approach I used is

1. Read in the grid into a vector.

2. Construct graph with vertices numbered 0-25 where x -> y if and only if y — 'A is seen directly above x — 'A' at least once in the grid.

3. Run topological sort on the graph.

4. Print the result.

There must be an implementation mistake on your part, which will be hard for other people to spot.

My code:

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

using ll = long long;
using ld = long double;
#define MAX(type) numeric_limits<type>::max()
#define MIN(type) numeric_limits<type>::min()

void dfs(int s);

int r, c;
vector<string> g;
vector<bool> seen;
vector<vector<int>> adj;
vector<vector<bool>> adjM;
vector<int> state;
string ans;
bool isPossible;

void dfs(int s) {
    if (state[s] == 2) {
        return;
    } else if (state[s] == 1) {
        isPossible = false;
        return;
    }
    state[s] = 1;

    for (auto u : adj[s]) {
        dfs(u);
    }
    state[s] = 2;
    ans += 'A' + s;
}

void solve() {
    cin >> r >> c;
    g.resize(r);
    seen.resize(26, false);
    for (int i = 0; i < r; i++) {
        cin >> g[i];
        for (int j = 0; j < c; j++) {
            seen[g[i][j] - 'A'] = true;
        }
    }

    adj.resize(26);
    adjM.resize(26, vector<bool>(26, false));
    for (int i = 1; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (g[i - 1][j] != g[i][j] &&
                !adjM[g[i][j] - 'A'][g[i - 1][j] - 'A']) {
                adj[g[i][j] - 'A'].push_back(g[i - 1][j] - 'A');
                adjM[g[i][j] - 'A'][g[i - 1][j] - 'A'] = true;
            }
        }
    }

    state.resize(26, 0);
    ans = "";
    isPossible = true;
    for (int i = 0; i < 26; i++) {
        if (seen[i]) {
            dfs(i);
        }
    }

    if (isPossible) {
        reverse(ans.begin(), ans.end());
        cout << ans << "\n";
    } else {
        cout << -1 << "\n";
    }

    // Need to reset for the next test case!
    g.clear();
    seen.clear();
    adj.clear();
    adjM.clear();
    state.clear();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        cout << "Case #" << i << ": ";
        solve();
    }
    return EXIT_SUCCESS;
}