When you are at one column and try to decide which row in the next column is best, ... you can add another check in case there are more than one row with best values right, and pick the row with the smaller value.
I think the only gotcha there is that the row can wrap around from the last row to 0. On 12/6/06, mukesh tiwari <[EMAIL PROTECTED]> wrote: > > hi friends i am try to solving this question > http://online-judge.uva.es/p/v1/116.html > for this problem i use left to right dynamic programming so i m getting > the total minimum cost but i m not getting how to find out lexicographically > shortest path .here is my code .....if u can change it fine but plz suggest > me algorithm to find lexicographically shortest path. > my program works fine if one path exist but if more than one path exist > then it's not giving lexicographically smallest path.what i m doing is > i m finding last column(n-1) minimum value and note down the row number > (let it be i).now in second last column(n-2) i searched out minmium value in > row i-1,i and i+1 becoz of problem property. and i keep doing this until i > reach the 0th column.doing this i m not getting what i suppose to find > out ...lexicographically smallest path.plz help... > > > #include<stdio.h> > > int min1(int k,int m,int n) > { > int min; > min=k; > if(min>m) > min=m; > if(min>n) > min=n; > return(min); > } > main() > { > > int > m1[100][100],a[100][100],i,j,m,n,min,k,arr[100],t,min2,t1,t2,t3; > while(scanf("%d%d",&m,&n)==2) > { > for(i=0;i<m;i++) > for(j=0;j<n;j++) > scanf("%d",&a[i][j]); > > for(i=0;i<m;i++) > m1[i][0]=a[i][0]; > for(j=1;j<n;j++) > for(i=0;i<m;i++) > > m1[i][j]=a[i][j]+min1(m1[(i+m-1)%m][j-1],m1[i][j-1],m1[(i+1)%m][j-1]); > > /*for(i=0;i<m;i++) > { > for(j=0;j<n;j++) > printf("%d ",m1[i][j]); > printf("\n"); > }*/ > //printf("\n"); > min2=m1[0][n-1]; > k=0; > for(i=1;i<m;i++) > if(m1[i][n-1]<min2) > { > min2=m1[i][n-1]; > k=i; > > } > //printf("k=%d min=%d\n",k+1,min2); > arr[n-1]=k; > > for(j=n-2;j>=0;j--) > { > min=m1[(arr[j+1]+m-1)%m][j]; > t=(arr[j+1]+m-1)%m; > if(min>m1[arr[j+1]][j]) > { > min=m1[arr[j+1]][j]; > t=arr[j+1]; > > } > > if(min>m1[(arr[j+1]+1)%m][j]) > { > min=m1[(arr[j+1]+1)%m][j]; > t=(arr[j+1]+1)%m; > > } > > arr[j]=t; > //printf("min=%d arr[%d]=%d\n",min,j,t); > } > for(i=0;i<=n-1;i++) > printf("%d ",arr[i]+1); > printf("\n%d\n",min2); > } > } > > > > > -- Fear of the LORD is the beginning of knowledge (Proverbs 1:7) --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
