Ruudukko

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long

using namespace std;

char mini[6666];
int n, qaq[2525][2525];
string s[101010];
queue<pair<char, pair<int,int>>> q[101010];

int main() {
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	cin >> n;
	for(int i=0; i<n; i++)
		cin >> s[i];
	for(int i=0; i<6666; i++)
		mini[i] = 'Z';
	q[0].push(make_pair(s[0][0], make_pair(0,0)));
	mini[0] = s[0][0];
	for(int i=0; i<6666; i++) {
		while(!q[i].empty()) {
			char taa = q[i].front().first;
			int x = q[i].front().second.second;
			int y = q[i].front().second.first;
			q[i].pop();
			if(taa>mini[i]||qaq[y][x])
				continue;
			qaq[y][x] = 1;
			if(x+1<n) {
				q[i+1].push(make_pair(s[y][x+1], make_pair(y, x+1)));
				mini[i+1] = min(mini[i+1], s[y][x+1]);
			}
			if(y+1<n) {
				q[i+1].push(make_pair(s[y+1][x], make_pair(y+1, x)));
				mini[i+1] = min(mini[i+1], s[y+1][x]);
			}
		}
	}
	for(int i=0; i<n*2-1; i++)
		cout << mini[i];
}

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: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED