main.c

设平面上有一个m&acute n的网格

#include <stdio.h>
#include <time.h>
#include <stdlib.h>


int a[10][10]={0};
int b[10][10]={0};
int grid[11][11]={0};

int print(int i,int j,int m,int n)
{
    if(i==m-1&&j==n-1)
    {
        printf("(%d,%d)\n",i,j);
    }
    else
    {
        printf("(%d,%d) ",i,j);
    }
    if(grid[i][j]==0)
    {
        return 0;
    }
    else
    {
        if(grid[i][j]-a[i][j]==grid[i+1][j])
        {
            print(i+1,j,m,n);
        }
        else if(grid[i][j]-b[i][j]==grid[i][j+1])
        {
            print(i,j+1,m,n);
        }
    }
}

int main()
{
    int sum=0;
    int i;
	int j;
	int m,n;


	printf("输入m(m<10):");                      //输入m，n
	scanf("%d",&m);
	printf("输入n(n<10)：");
	scanf("%d",&n);

	srand((int)time(0));

	for(i=0;i<m-1;i++)                   //随机产生向上移动代价
	{
	    for(j=0;j<n;j++)
	    {
	        a[i][j]=1+(int)(10.0*rand()/(RAND_MAX+1.0));
	    }
	}

	for(i=0;i<m;i++)                   //随机产生向右移动代价
	{
	    for(j=0;j<n-1;j++)
	    {
	        b[i][j]=1+(int)(10.0*rand()/(RAND_MAX+1.0));
	    }
	}

	grid[m-1][n-1]=0;
	sum=0;
	for(i=n-2;i>=0;i--)
	{
	    sum+=b[m-1][i];
	    grid[m-1][i]=sum;
	}
	sum=0;
	for(i=m-2;i>=0;i--)
	{
	    sum+=a[i][n-1];
	    grid[i][n-1]=sum;
	}
	for(i=m-2;i>=0;i--)
	{
	    for(j=n-2;j>=0;j--)
	    {
	        grid[i][j]=((grid[i+1][j]+a[i][j])>(grid[i][j+1]+b[i][j]))? (grid[i][j+1]+b[i][j]):(grid[i+1][j]+a[i][j]);
	    }
	}

	print(0,0,m,n);



	return 0;
}