Ruudukko

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>

using namespace std;

/* string etsi(const vector<vector<char>> &ruudukko, int i, int j, int n) {
    string merkkijono;
    merkkijono += ruudukko[i][j];

    if (i == n - 1 and j == n - 1) {
        return merkkijono;
    } else if (i == n - 1 and j < n - 1) {
        merkkijono += etsi(ruudukko, i, j + 1, n);
    } else if (j == n - 1 and i < n - 1) {
        merkkijono += etsi(ruudukko, i + 1, j, n);
    } else {
        if (ruudukko[i + 1][j] < ruudukko[i][j + 1]) {
            merkkijono += etsi(ruudukko, i + 1, j, n);
        } else if (ruudukko[i + 1][j] > ruudukko[i][j + 1]) {
            merkkijono += etsi(ruudukko, i, j + 1, n);
        } else {
            string m1 = etsi(ruudukko, i, j + 1, n);
            string m2 = etsi(ruudukko, i + 1, j, n);

            if (m1 < m2) {
                merkkijono += m1;
            } else {
                merkkijono += m2;
            }
        }
    }

    return merkkijono;
} */

int main() {
    cin.sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    vector<vector<char>> ruudukko(n);

    for (int i = 0; i < n; i++) {
        ruudukko[i] = vector<char>(n);
        for (int j = 0; j < n; j++) {
            char kirjain;
            cin >> kirjain;
            if (kirjain == '\n') {
                j--;
                continue;
            }
            ruudukko[i][j] = kirjain;
        }
    }

    string m;
    vector<pair<int, int>> haettavat;
    haettavat.push_back(make_pair(0, 0));

    while (true) {
        vector<pair<int, int>> uudet;
        char pienin = 'Z';
        for (auto p : haettavat) {
            if (p.first >= n or p.second >= n) {
                continue;
            }

            char merkki = ruudukko[p.first][p.second];
            if (merkki < pienin) {
                pienin = merkki;
                uudet.clear();
            }

            if (merkki == pienin) {
                if (p.first + 1 < n) {
                    uudet.push_back(make_pair(p.first + 1, p.second));
                }

                if (p.second + 1 < n) {
                    uudet.push_back(make_pair(p.first, p.second + 1));
                }
            }
        }

        m += pienin;

        if (uudet.size() == 0) {
            break;
        }

        haettavat = uudet;
    }

    cout << m << "\n";

    return 0;
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED