UVA 116 Solution CPP code

Create two arrays in addition to the input array. One is the DP array, and one is the path array. dp[i][j] = in[i][j] + min(dp[i-1][j-1], dp[i][j-1], dp[i+1][j-1]). Make sure that you wrap around the top and bottom of the matrix (use modulo, or just an if statement).

For the path, you must keep an array of strings (or whatever you like) to hold the current path to that point. Prefer lexicographically shorter paths when two DP cells have the same value. Note that lexicographically shorter in this problem means that you minimize the row number, and not the ASCII value of the string. For example:

1 10 10 10
1 2 3 4

In ASCII terms, and normal string comparison terms, the first string is lexicographically earlier. But in this problem, they want the latter.

Remember it does not matter you from left to right or right to left.

CODE:

#include<stdio.h>


#define MIN(a,b) a<b? a:b
#define maxe 1<<30

int p[11][101],r,c;



int main(){


    int i,j,rp;
    long long a[11][101],tmp,min,f;

 while(scanf("%d %d",&r,&c)!=EOF){

     for(i=0;i<r;i++)
     for(j=0;j<c;j++)
     scanf("%lld",&a[i][j]);

    for(j=c-2;j>=0;j--)
    for(i=0;i<r;i++){

        tmp=a[i][j];

        rp=i-1;
        if(rp<0)rp=r-1;
        a[i][j]=tmp+a[rp][j+1];
        p[i][j]=rp;



        rp=i;f=1;
        if(a[i][j]>tmp+a[rp][j+1]||(a[i][j]==tmp+a[rp][j+1]&&i==0)){
        a[i][j]=tmp+a[rp][j+1];
        p[i][j]=rp;
        f=0;
        }


        rp=i+1;
        if(rp==r)rp=0;
        if(a[i][j]>tmp+a[rp][j+1]||(a[i][j]==tmp+a[rp][j+1]&&i==0&&f)||(a[i][j]==tmp+a[rp][j+1]&&i==r-1)){
        a[i][j]=tmp+a[rp][j+1];
        p[i][j]=rp;
        }



        }

     min=maxe;
     for(i=0;i<r;i++){
        if(min>a[i][0]){
        min=a[i][0];
        rp=i;
        }
     }

    for(j=0;j<c;j++){

        printf("%d",rp+1);
        if(j<c-1)printf(" ");
        rp=p[rp][j];
        }

    printf("\n%lld\n",min);


     }

}