Ruudukko

#include <iostream>
#include <queue>
#include <utility>
#include <string>

using namespace std;
#define N 2501
char grid[N][N];
bool goingTo[N][N];
queue<pair<int, int>> q;
string best = "";
int n;

void BFS() {
	// Start from (0, 0)
	q.push({0, 0});
	best += grid[0][0];
	while (!q.empty()) {
		// Figure the out the best character.
		char bestR = '|';
		queue<pair<int,int>> possible;
		while (!q.empty()) {
			auto c = q.front(); q.pop();
			int y = c.first, x = c.second;
			// Down.
			if (grid[y + 1][x] && !goingTo[y + 1][x]) {
				possible.push({y + 1, x});
				goingTo[y + 1][x] = true;
				if (bestR > grid[y + 1][x]) bestR = grid[y + 1][x];
			}
			// Right.
			if (grid[y][x + 1] && !goingTo[y][x + 1]) {
				possible.push({y, x + 1});
				goingTo[y][x + 1] = true;
				if (bestR > grid[y][x + 1]) bestR = grid[y][x + 1];
			}
		}
		// <q> will be empty. We figured the best routes to go towards.
		
		// Fill <q> again with the (distinct) ones that led to the best route.
		while (!possible.empty()) {
			auto t = possible.front(); possible.pop();
			if (grid[t.first][t.second] == bestR) q.push(t); // This is one of the best routes.
		}
		
		if (bestR != '|') best += bestR; // Atleast one is going the best route, so add it.
	}
}

int main(int argc, char** argv) {
	cin >> n; cin.ignore();
	for (int i = 0; i < n; i++) {
		string s; cin >> s; cin.ignore();
		for (int j = 0; j < n; j++) {
			grid[i][j] = s[j];
		}
	}
	BFS();
	cout << best;
	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: 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