起点博客

貌似是中兴出的题目，原题如下：

伊万洛夫在比武大会上力克群雄，成为新一届“草原雄鹰”，为部落赢得了莫大荣誉。首领决定要重重奖赏，他对伊万洛夫说：“孩子，你是知道的，面前的这片草原，南北向和东西向的道路纵横交错。现在，路口放着纯金打造的俄罗斯娃娃，重量大小不等，重的都能装下轻的。你可以沿着道路飞奔，拾取路口的娃娃，要求是任何时刻必须是一个套娃，装好后就不能再拆开了。注意不要走重复路。”
请你为伊万洛夫规划路线，使得他能够有最大的收获。
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    5

1   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);
}