Ruudukko

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 501;
 
int n;
string m[N];
int r[N][N];
// 1 = start
// 2 = x-1
// 3 = y-1
 
int main()
{
    cin>>n;
    string s;
    for(int i=0;i<n;i++)
    {
        cin>>s;
        m[i] = s;
    }
    for(int x=0;x<n;x++)
    {
        for(int y=0;y<n;y++)
        {
            if(x==0 && y==0) r[x][y] = 1;
            else if(x==0) r[x][y] = 3;
            else if(y==0) r[x][y] = 2;
            else
            {
                pair<int,int> lpos;
                lpos.first = x-1;
                lpos.second = y;
                pair<int,int> upos;
                upos.first = x;
                upos.second = y-1;
                while(m[lpos.first][lpos.second] == m[upos.first][upos.second])
                {
                    if(lpos.first==0 && lpos.second==0 && upos.first==0 && upos.second==0) break;
 
                    int x = 3 - r[lpos.first][lpos.second];
                    int y = r[lpos.first][lpos.second] - 2;
                    lpos.first -= x;
                    lpos.second -= y;
 
                    x = 3 - r[upos.first][upos.second];
                    y = r[upos.first][upos.second] - 2;
                    upos.first -= x;
                    upos.second -= y;
                }
                if(m[lpos.first][lpos.second] < m[upos.first][upos.second]) r[x][y] = 2;
                else r[x][y] = 3;
            }
        }
    }
    int x = n-1;
    int y = n-1;
    string result = "";
    while(x>=0 && y>=0)
    {
        result += m[x][y];
        int xc = 3 - r[x][y];
        int yc = r[x][y] - 2;
        x -= xc;
        y -= yc;
    }
    reverse(result.begin(), result.end());
    cout<<result;
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: WRONG ANSWER

Test 4

Group: 1

Verdict: WRONG ANSWER

Test 5

Group: 1

Verdict: WRONG ANSWER

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: WRONG ANSWER

Test 9

Group: 2

Verdict: WRONG ANSWER

Test 10

Group: 2

Verdict: WRONG ANSWER

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: WRONG ANSWER

Test 14

Group: 3

Verdict: WRONG ANSWER

Test 15

Group: 3

Verdict: WRONG ANSWER