#include <iostream>

/*мінімальне значення для позначення якщо неможливо здійснити рух вгору, вправо або по діагоналі*/
#define C -9999

/*
2 -1 3 3 -2 -3 4 2
-1 2 -2 -1 4 2 -3 2
2 -1 5 3 -1 2 -1 3
1 -2 5 3 3 -2 -4 6
-2 4 -2 3 -5 1 -3 -4
-3 -2 -1 -5 3 1 -3 -2
-2 -3 -2 3 -2 3 -1 -5
3 -1 -2 -3 -2 -1 4 5
*/

using namespace std;

int main() {

    /*n - розмір масиву*/
    /*u, r, d - значення для визначення максимального*/

    int n, u, r, d;

    cout << "Enter n: ";
    cin >> n;
    cout << endl;

    int map[n][n], maxMap[n][n];

    /*map - масив значень*/
    /*maxMap - масив максимальних значень*/

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

    /*ініціалізуємо кінцеву точку*/
    maxMap[0][n - 1] = map[0][n - 1];

    /*обраховуємо максимальні значення*/
    /*йдемо з кінцевої клітинки до початкової*/
    for (int i = 0; i < n; i++) {
        for (int j = n - 1; j >= 0; j--) {
            if (not (i == 0 && j == n - 1)) {
                u = r = d = C;

                /*якщо можливий рух вгору*/
                if (i - 1 >= 0) {
                    u = maxMap[i - 1][j];
                }

                /*якщо можливий рух вправо*/
                if (j + 1 < n) {
                    r = maxMap[i][j + 1];
                }

                /*якщо можливий рух по діагоналі*/
                if (j + 1 < n && i - 1 >= 0) {
                    d = maxMap[i - 1][j + 1];
                }

                /*записуємо максимальне значення*/
                maxMap[i][j] = map[i][j] + max(u, max(r, d));
            }
        }
    }

    /*йдемо з першої клітинки до кінцевої*/
    int i = n - 1, j = 0;

    cout << endl << "Way: ";

    /*доки теперішня клітина != кінцевій*/
    while (not (i == 0 && j == n - 1)) {
        u = r = d = C;

        /*якщо можливий рух вгору*/
        if (i - 1 >= 0) {
            u = maxMap[i - 1][j];
        }

        /*якщо можливий рух вправо*/
        if (j + 1 < n) {
            r = maxMap[i][j + 1];
        }

        /*якщо можливий рух по діагоналі*/
        if (j + 1 < n && i - 1 >= 0) {
            d = maxMap[i - 1][j + 1];
        }

        /*рухаємось вгору якщо це max*/
        if (u == max(u, max(r, d))) {
            cout << "U";
            i--;
        }

        /*рухаємось вправо якщо це max*/
        if (r == max(u, max(r, d))) {
            cout << "R";
            j++;
        }

        /*рухаємось по діагоналі якщо це max*/
        if (d == max(u, max(r, d))) {
            cout << "D";
            i--; j++;
        }
    }

    cout << endl << "Max score: " << maxMap[n - 1][0] << endl;
    cout << endl << "Map of max values:" << endl;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cout << maxMap[i][j] << " ";
        cout << endl;
    }

    return 0;
}