2353.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#define debug 0
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define NMAX 501
#define INF 2000000001
long m[NMAX][NMAX]={0};
long a[NMAX][NMAX]={0};
long M,N;
long b[NMAX*NMAX]={0};
int xp[3]={-1,0,1},yp[3]={0,-1,0};
void solve()
{
	int i,j;
	for(i=1;i<=N;i++)
	{
		m[1][i]=a[1][i];
	}
	for(i=2;i<=M;i++)
	{
		for(j=1;j<=N;j++)
		{
			if(m[i][j]>a[i][j]+m[i-1][j])
				m[i][j]=a[i][j]+m[i-1][j];
		}
		for(j=2;j<=N;j++)
		{
			if(m[i][j]>a[i][j]+m[i][j-1])
				m[i][j]=a[i][j]+m[i][j-1];
		}
		for(j=N-1;j>=1;j--)
		{
			if(m[i][j]>a[i][j]+m[i][j+1])
				m[i][j]=a[i][j]+m[i][j+1];
		}
	}
}
void output()
{
	int kx,ky,i;
	long min=INF;
	int index=1;
	long q=0;
	for(i=1;i<=N;i++)
	{
		if(min>m[M][i])
		{
			min=m[M][i];
			index=i;
		}
	}
	ky=M;
	kx=index;
	b[q++]=kx;
	ky--;
	if(M==1)
	{
		printf("%d",kx);
		return ;
	}
	while(1)
	{
		b[q++]=kx;
		if(ky==1)
			break;
		for(i=0;i<3;i++)
		{
			if(kx+xp[i]<1||kx+xp[i]>N)
				continue;
			if(m[ky][kx]==a[ky][kx]+m[ky+yp[i]][kx+xp[i]])
			{
				ky=ky+yp[i];
				kx=kx+xp[i];
				break;
			}
		}
	}
	for(i=q-1;i>=0;i--)
		printf("%d\n",b[i]);
		

}
main()
{
#if debug 	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	scanf("%d%d",&M,&N);
	int i,j;
	for(i=1;i<=M;i++)
		for(j=1;j<=N;j++)
		{
			scanf("%d",&a[i][j]);
			m[i][j]=INF;
		}
	solve();
	output();
#if debug
	fclose(stdin);
	fclose(stdout);
#endif;
	return 1;
}