Ruudukko

#include <bits/stdc++.h>

#define N (1<<17)
#define ll long long
#define ld long double
#define M 1000000007
#define INF 0x5ADFACE5
#define LINF 0x51DEEFFEC7C0DECALL
#define pii pair<int, int>
#define pll pair<long long, long long>
#define F first
#define S second

using namespace std;

int f[2555][2555];
int e[2555][2555];
char c[2555][2555];

int main () {
	cin.sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin>>n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) cin>>c[i][j];
	}
	vector<pii> v = {{0, 0}};
	string ans;
	ans.push_back(c[0][0]);
	while (!v.empty()) {
		vector<pii> q;
		char mn = 'Z' + 1;
		for (pii p : v) {
			int y = p.F;
			int x = p.S;
			if (c[y + 1][x] && !e[y + 1][x]) {
				q.push_back({y + 1, x});
				e[y + 1][x] = 1;
				f[y + 1][x] = 1;
				mn = min(mn, c[y + 1][x]);
			}
			if (c[y][x + 1] && !e[y][x + 1]) {
				q.push_back({y, x + 1});
				e[y][x + 1] = 1;
				f[y][x + 1] = 2;
				mn = min(mn, c[y][x + 1]);
			}
		}
		v.clear();
		if (mn <= 'Z') ans.push_back(mn);
		for (pii p : q) {
			if (c[p.F][p.S] == mn) {
				v.push_back(p);
			}
		}
	}
	cout<<ans<<endl;
}

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