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;

bool inRange(const pair<int,int> c) {
	return ((0 <= c.first) && (c.first < n)) && ((0 <= c.second) && (c.second < n));
}

void BFS() {
	// Start from (0, 0)
	q.push({0, 0});
	int moves = (n * n) - ((n - 1) * (n - 1));
	int m = 0;
	while (m != moves) {
		char bestR = '|';
		queue<pair<int,int>> s;
		while (!q.empty()) {
			pair<int,int>c=q.front();q.pop();s.push(c);
			char cur = grid[c.first][c.second];
			if (cur < bestR) bestR = cur;
		}
		while(!s.empty()) {
			pair<int,int>c=s.front();s.pop();
			char cur = grid[c.first][c.second];
			if (cur==bestR) {
				// This is a one, we should continue.
				pair<int,int>r={c.first,c.second+1};
				pair<int,int>d={c.first+1,c.second};
				if (inRange(r)) q.push(r);
				if (inRange(d)) q.push(d);
			}
		}
		best+=bestR;
		m++;
	}
}

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: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED