Ruudukko

#include <bits/stdc++.h>

#define ll long long
#define INF 999999999
#define pii pair<int, int>

using namespace std;

bool b[2001][2001];
char c[2001][2001];
char d[4001];

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

	for (int i = 0; i <= 4000; i++) d[i] = 'z';

	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) cin>>c[y][x];
	}
	d[0] = c[0][0];

	queue<pair<pii, int>> q;
	q.push({{0, 0}, 0});
	while (!q.empty()) {
		int y = q.front().first.first;
		int x = q.front().first.second;
		int i = q.front().second;
		q.pop();
		if (b[y][x] || c[y][x] != d[i]) continue;
		b[y][x] = 1;
		if (y < n - 1) {
			q.push({{y + 1, x}, i + 1});
			d[i + 1] = min(d[i + 1], c[y + 1][x]);
		}
		if (x < m - 1) {
			q.push({{y, x + 1}, i + 1});
			d[i + 1] = min(d[i + 1], c[y][x + 1]);
		}
	}

	int y = n - 1;
	int x = m - 1;
	string ans = "";
	while (y || x) {
		ans.push_back(c[y][x]);
		if (y) {
			if (b[y - 1][x]) y--;
			else x--;
		} else x--;
	}
	ans.push_back(c[0][0]);
	reverse(ans.begin(), ans.end());
	cout<<ans<<endl;
}