俄罗斯套娃问题的C语言解
貌似是中兴出的题目，原题如下：
伊万洛夫在比武大会上力克群雄，成为新一届“草原雄鹰”，为部落赢得了莫大荣誉。首领决定要重重奖赏，他对伊万洛夫说：“孩子，你是知道的，面前的这片草原，南北向和东西向的道路纵横交错。现在，路口放着纯金打造的俄罗斯娃娃，重量大小不等，重的都能装下轻的。你可以沿着道路飞奔，拾取路口的娃娃，要求是任何时刻必须是一个套娃，装好后就不能再拆开了。注意不要走重复路。”
请你为伊万洛夫规划路线，使得他能够有最大的收获。
Input: cross.txt
输入包括多组测试用例；
每个测试用例开始是一对整数<R, C>，R表示东西向道路数，C表示南北向道路总数；接下来R行，每行包括C个正整数W[r,c] ，分别表示第r条东西向道路与第c条南北向道路交叉处路口放置的俄罗斯娃娃的重量。
Output:
输出能有最大收获的路径规划。
假设1：
cross.txt
2 7
1 2 13 6 7 12 11
14 3 4 5 8 9 10
输出：
1 2 3 4 5 6 7 8 9 10 11 12
假设2：
cross.txt
5 51 16 15 14 13
2 17 24 23 12
3 18 25 22 11
4 19 20 21 10
5 6 7 8 9
输出：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
注释:
1)从<0,0>出发;
2)路线不能重复;
3)不要求最后回到出发点。
貌似很多人都想到了递归方法的实现，由于对于递归使用很少，没有把握，就使用以前维特比译码相类似的方法。直接放代码，代码质量较差，见谅。
/* http://xinzero.com will@xinzero.com */ #include <stdio.h> #include <stdlib.h> struct stat{ int met; //profit int value; int x; int y; stat *plast; }; void main() { int *pint=NULL,*pInit=NULL; stat *pPath=NULL,*pSta=NULL,*pMax=NULL; int row=0,col=0; int i=0,j=0,k=0; int m=0,n=0,l=0; int imax=0; int M=0,R=0; printf("input R,C value:"); scanf_s("%d %d",&row,&col); printf("[R,C]=[%d,%d]\r\n",row,col); pInit = (int*)malloc(sizeof(int)*row*col); pint = pInit; for(i=0;i<row;i++) { for(j=0;j<col;j++) { scanf_s("%d",pint++); } } pint = pInit; printf("The path\r\n"); for(i=0;i<row;i++) { for(j=0;j<col;j++) { printf("%d ",*pint++); } printf("\r\n"); } pint = pInit; pPath = (stat*)malloc(sizeof(stat)*row*row*col*col); pSta = pPath; for(i=0;i<row*col*row*col;i++) { pSta->met =-1; pSta->value = 0; pSta->plast =NULL; pSta++; } pSta = pPath; pSta->met = *pint; pSta->value = *pint; pSta->x=0; pSta->y=0; i=j=0; for(k=1;k<row*col;k++) { M = 0; for(l=0;l<row*col;l++) { m = l*row*col+k; //current valid if(pSta[m-1].met==-1) { continue; } else { i = pSta[m-1].x; j = pSta[m-1].y; printf("i=%d,j=%d",i,j); if((i+1)<row) { n = (i+1)*col + j; if(pint[n]>pSta[m-1].value) { R = M*row*col + k; pSta[R].met = pSta[m-1].met + pint[n]; pSta[R].value = pint[n]; pSta[R].x = i+1; pSta[R].y = j; pSta[R].plast = &pSta[m-1]; printf("[%d,%d],%d,met:%d",i+1,j,R,pSta[R].met); M++; } } if((i-1)>=0) { n = (i-1)*col + j; if(pint[n]>pSta[m-1].value) { R = M*row*col + k; pSta[R].met = pSta[m-1].met + pint[n]; pSta[R].value = pint[n]; pSta[R].x = i-1; pSta[R].y = j; pSta[R].plast = &pSta[m-1]; printf("[%d,%d],%d,met:%d",i-1,j,R,pSta[R].met); M++; } } if((j+1)<col) { n = i*col + j+1; if(pint[n]>pSta[m-1].value) { R = M*row*col + k; pSta[R].met = pSta[m-1].met + pint[n]; pSta[R].value = pint[n]; pSta[R].x = i; pSta[R].y = j+1; pSta[R].plast = &pSta[m-1]; printf("[%d,%d],%d,met:%d",i,j+1,pSta[R],pSta[R].met); M++; } } if((j-1)>=0) { n = i*col + j-1; if(pint[n]>pSta[m-1].value) { R = M*row*col + k; pSta[R].met = pSta[m-1].met + pint[n]; pSta[R].value = pint[n]; pSta[R].x = i; pSta[R].y = j-1; pSta[R].plast = &pSta[m-1]; printf("[%d,%d],%d,met:%d",i,j-1,pSta[R],pSta[R].met); M++; } } printf("\r\n"); } } printf("\r\n"); } for(k=row*col-1;k>=0;k--) { for(l=0;l<row*col;l++) { m = l*row*col+k; //printf("%d,%d,",m,pSta[m].met); if(pSta[m].met==-1) { continue; } else { if(imax<pSta[m].met) { imax = pSta[m].met; pMax = &pSta[m]; printf("imax:%d\n",imax); } } } } pint = pInit; i=0; //do while(pMax->plast!=NULL) { *pint = pMax->value; pMax = pMax->plast; printf("%d,%d ",i,*pint); pint++; i++; }//while(pMax->plast!=NULL); *pint = pMax->value; pMax = pMax->plast; printf("%d,%d ",i,*pint); pint++; i++; printf("\r\n"); pint = pInit; while(i>0) { printf("%d ",pint[i-1]); i--; } printf("\r\n"); //system("pause"); free(pInit); free(pPath); }
Recent Comments