编辑代码

#include<stdio.h>

#define MAX 10
int m,n;  //方格的行和列
int arr[MAX][MAX]; //储存原始方格元素
int F[MAX][MAX]; //保存收集到的最大硬币数
int H[MAX][MAX];//进行回溯操作时，保存路线坐标

void HuiSu();
void FindMax();
int Max(int a,int b);
/*
方格为：
		0 0 0 0 1 0
		0 1 0 1 0 0
		0 0 0 1 0 1
		0 0 1 0 0 1
		1 0 0 0 1 0
*/
void main()
{
	printf("请输入方格的行数和列数：(空格隔开)\n");
	scanf("%d%d",&m,&n);
	for(int i=1;i<=m;i++)
	{
		printf("请输入第%d行的%d个数：(只能出现0或1)\n",i,n);
		for(int j=1;j<=n;j++)
		{
			scanf("%d",&arr[i][j]);
		}
	}
		FindMax();
		printf("收集的路线为：\n");
		HuiSu();
}

int Max(int a,int b)
{
	return a>=b? a:b;
}

void FindMax()
{
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			F[i][j]=Max(F[i-1][j],F[i][j-1])+arr[i][j];
		}
	}
		printf("\n最多搜集 %d 个硬币。\n",F[m][n]);
}


void HuiSu()
{
	int a=m;
	int b=n;
	H[1][1]=1;
	H[m][n]=1;
	while(a>=1&&b>=1)
	{
		if(F[a-1][b]>=F[a][b-1])
		{
			H[a-1][b]=1;
			a--;
		}
		else
		{
			H[a][b-1]=1;
			b--;
		}
	}
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
		{
			if(H[i][j]==1)
			{
				if(i==m&&j==n)
					printf("（%d，%d）\n",m,n);
				else
					printf("（%d，%d）-->",i,j);
			}
		}
}