15. Mouse and corns

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define mp make_pair
#define pb push_back

const int N = 1000;
const int INF = (int)1e18;

int dp[N][N];
pair<int,int> parent[N][N];

signed main()
{
    ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    int n,m;
    cin >> n >> m;

    for(int i=n;i>=1;i--)
    {
        for(int j=1;j<=m;j++)
        {
            cin >> dp[i][j];
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(i == 1 && j == 1)
                continue;
            if(i == 1)
            {
                dp[i][j] += dp[i][j-1];
                parent[i][j].first = 0;
                parent[i][j].second = -1;
                continue;
            }
            if(j == 1)
            {
                dp[i][j] += dp[i-1][j];
                parent[i][j].first = -1;
                parent[i][j].second = 0;
                continue;
            }
            if(dp[i-1][j] > dp[i][j-1])
            {
                dp[i][j] += dp[i-1][j];
                parent[i][j].first = -1;
                parent[i][j].second = 0;
            }
            else
            {
                dp[i][j] += dp[i][j-1];
                parent[i][j].first = 0;
                parent[i][j].second = -1;
            }
        }
    }

    int x,y;
    int dx,dy;

    x = n, y = m;

    stack<char> st;

    while(x != 1 || y != 1)
    {
        dx = parent[x][y].first;
        dy = parent[x][y].second;
        if(dx == -1)
            st.push('F');
        else
            st.push('R');
        x += dx;
        y += dy;
    }

    while(!st.empty())
    {
        cout << st.top();
        st.pop();
    }

    return 0;
}