paste bin

malic
C++
#include <cstdio>

int main(void)
{
    char *path,**dir;
    int **map, N,M,i,j;

    // deal with the input data
    // and init

    // you can define path[201],dir[100][100]
    // instead of use "new" operator
    scanf("%d%d",&M,&N);
    path=new char [M+N+2];
    dir=new char* [M];
    map=new int*  [M];
    for(i=0;i<M;i++)
    {
        map[i]=new int [N];
        dir[i]=new char [N];
    }
    for(i=0;i<M;i++)
        for(j=0;j<N;j++)
            scanf("%d",&map[i][j]);

    // init dynamic programming
    dir[M-1][0]='S';//start, this char is useless.
    for(i=M-2;i>=0;i--)
    {
        map[i][0]+=map[i+1][0];
        dir[i][0]='F';
    }
    for(i=1;i<N;i++)
    {
        map[M-1][i]+=map[M-1][i-1];
        dir[M-1][i]='R';
    }

    //dynamic programming
    
    for(i=M-2;i>=0;i--)
    {
        for(j=1;j<N;j++)
        {
            if(map[i+1][j]>map[i][j-1])
            {
                map[i][j]+=map[i+1][j];
                dir[i][j]='F';
            }
            else
            {
                map[i][j]+=map[i][j-1];
                dir[i][j]='R';
            }
        }
    }

    for(i=0;i<M;i++)
        delete [] map[i];
    delete [] map;

    // recode the path
    i=0;
    j=N-1;
    int k=0;
    while(1)
    {
        if(dir[i][j]=='F')
        {
            path[k++]='F';
            i++;
        }
        else
        {
            path[k++]='R';
            j--;
        }
        if (i==M-1 && j==0)
            break;
    }
    while(k>0)
    {
        printf("%c",path[--k]);
    }
    printf("\n");

    delete [] path;
    for(i=0;i<M;i++)
        delete [] dir[i];
    delete [] dir;
    return 0;
}

2019 C3QE

fork this code