Ruudukko

#include <iostream>
#include <string>

char grid[2500][2500];

using namespace std;

string ret;

void tree(int x, int y, int n, string h)
{
	if(x == n - 1 && y == n - 1)
	{
		if(h < ret || ret == "")
			ret = h;
		return;
	}

	if(x == n - 1 && y < n - 1)
		tree(x, y + 1, n, h + grid[x][y + 1]);
	else if(y == n - 1 && x < n - 1)
		tree(x + 1, y, n, h + grid[x + 1][y]);
	else if((int)grid[x + 1][y] < (int)grid[x][y + 1])
		tree(x + 1, y, n, h + grid[x + 1][y]);
	else if((int)grid[x][y + 1] < (int)grid[x + 1][y])
		tree(x, y + 1, n, h + grid[x][y + 1]);
	else if(x < n - 1 && y < n - 1)
	{
		tree(x + 1, y, n, h + grid[x + 1][y]);
		tree(x, y + 1, n, h + grid[x][y + 1]);
	}
}

int main()
{
	int n;
	cin >> n;

	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			cin >> grid[i][j];
		}
	}

	tree(0, 0, n, string(1, grid[0][0]));
	cout << ret << 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: 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