Ruudukko

#include <iostream>

using namespace std;

char ruudukko[510][510];
string paras[510][510];

int n;

string rakenna(int x, int y)
{
	if(paras[x][y] != "")
		return paras[x][y];

	char a = ruudukko[x + 1][y];
	char b = ruudukko[x][y + 1];

	if(a == 0)
		a = 127;

	if(b == 0)
		b = 127;

	string l;

	if(a < b)
	{
		l = rakenna(x + 1, y);
	}
	else if(b < a)
	{
		l = rakenna(x, y + 1);
	}
	else if(a != 127)
	{
		string as, bs;

		as = rakenna(x + 1, y);
		bs = rakenna(x, y + 1);

		if(as < bs)
			l = as;
		else
			l = bs;
	}

	string ans;
	ans.push_back(ruudukko[x][y]);
	ans.append(l);

	return paras[x][y] = ans;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	
	cin >> n;

	char all = 0;
	bool hyva = true;

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

			if(all == 0 || all == ruudukko[i][j])
			{
				all = ruudukko[i][j];
			}
			else
			{
				hyva = false;
			}
		}
	}

	if(hyva)
	{
		cout << string(n * 2 - 1, all) << endl;
		return 0;
	}


	cout << rakenna(0, 0) << 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: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED