拯救公主.cpp

来自「有关算法设计与分析的几个小程序（查找与替换问题、炒饭问题、寻宝问题等）」· C++ 代码 · 共 46 行

#include<stdio.h>
int A[20][20],m,n,bestA,total;

void save(int i,int j,int total)
{
	if(total<bestA)
		return;
	else if(i==n-1&&j==m-1)
	{
		if(total>bestA)
			bestA=total;
		return;
	}
	else if(i==n-1)
		save(i,j+1,total-A[i][j+1]);
    else if(j==m-1)
		save(i+1,j,total-A[i+1][j]);
	else 
	{
		save(i,j+1,total-A[i][j+1]);
		save(i+1,j,total-A[i+1][j]);
	}
}

main()
{
	int i,j,k=0,s;
	scanf("%d",&s);
	while(k<s)
	{
		scanf("%d%d",&n,&m);
		for(i=0;i<n;i++)
			for(j=0;j<m;j++)	
				scanf("%d",&A[i][j]);
        bestA=0;
		save(0,0,A[0][0]);
		if(bestA>0)
			printf("%d\n",bestA);
		else 
			printf("bad luck!\n");
		k++;
	}
	return 0;
}