博客

/*
N*M的矩阵迷宫中，放着不同价值的礼物，从（0，0）开始，只能向下或向右走。经过的每一个位置，
如果该位置的礼物价值大于你手上所有的礼物，则你可以选择拿该礼物（也可以不拿），直到（n-1, m-1）。
如果你的手上礼物个数恰好为K个，那么礼物归你。试问总共有多少总方案，使最后可以拿到k个礼物。
输入实例：
2 2 2
1 2
2 1
第一行为N M K（1<=N,M<=50, 1<=K<=12）
之后N行K列为礼物数值矩阵
输出：
2
*/




#include <iostream>
using namespace std;

//define the return type
typedef enum{
RT_OK,
RT_FAIL
}FPI_ERROR;

//define the way to make debuging  the code convinient
#define DEBUG
//#define RELEASE 

typedef unsigned int uint64;
uint64 K;
int  n_count = 0;


#ifdef DEBUG
#define MODULE_TEST 1
#else
#define MODULE_TEST 0
#endif

//define module log output
#define FPI_DEBUG(id,fmt,arg...) \
 if(id) \
 {\
 	printf(fmt,arg);\
 }\
 else \
 {\
    \
 }		
 

#ifdef DEBUG
int array[4][4]={1,2,3,2,1,4,2,3,5,2,4,2,3,2,5,6};
#else
int array[][];
#endif


FPI_ERROR startGetGifts(uint64 i,uint64 j,int value_max,uint64 n_gifts,uint64 N,uint64 M);


/*******************************
*Func. count the methed of getting K gifts.
*Aut. wmy
*Dtae. 2015.10.22
*param. @i @j the index of 2-d array.
@value_max the most value gift in your hand.
@n_gifts the number of gifts in your hand
*return RT_OK.
*********************************/
FPI_ERROR startGetGifts(uint64 i,uint64 j,int value_max,uint64 n_gifts,uint64 N,uint64 M)
{
	
    if (j == M-1 && i == N-1)
    {
       	n_gifts++;
    	 printf("overi=%d.j=%d.n=%d.\n",i,j,n_gifts);   	
        if(n_gifts == K){
          n_count++;
        }
        //printf("%d",RT_OK);
        return RT_OK;
    }	
   if(array[i][j] >= value_max && n_gifts < K)
   {
   	//get the gifts
	   	if(j < M-1)//go right
	   	startGetGifts(i,j+1,array[i][j],n_gifts+1,N,M);
	   	if(i < N-1)//go down 
	   	startGetGifts(i+1,j,array[i][j],n_gifts+1,N,M);
   }
   //don't get the gifts
    if(i != 0 && j != 0)
    {
	    if(j < M-1)
	   	startGetGifts(i,j+1,value_max,n_gifts,N,M);
	   	if(i < N-1)
	   	startGetGifts(i+1,j,value_max,n_gifts,N,M);	
    }	
}


int main()
{
	uint64 N=1,M=1;
#ifdef RELEASE
	cout<<"please input N:"<<endl;
	cin>>N;
	cout<<"please input M:"<<endl;
	cin>>M;
	cout<<"please input K:"<<endl;
cin>>K;
#else
	N=4;
	M=4;
	K=5;
#endif
	if(N < 1 || N >50 ||M <1 || M>50 || K<1 || K > 12)
	{
		 cout<<"the value input is error!"<<endl;
		 return RT_FAIL;
	}
	int length = N*M;
	int i;
	int j = 0;
#ifdef RELEASE
	for(i = 0;i < N;i++)
	{
		cout<<"please input the "<<i<<" line!"<<endl;
		for(;j < M; j++)
			cin>>array[i][j];
		j=0;
	}
#endif


#ifdef DEBUG 
	i=0;
	for(;i < length;i++)
	    cout<<array[i]<<" ";
	    cout<<endl;
#endif
	
	FPI_DEBUG(MODULE_TEST,"function:%s,start!\n",__FUNCTION__);
    startGetGifts(0,0,0,0,N,M);
    printf("%d\n",ret);
    FPI_DEBUG(MODULE_TEST,"function:%s,end!ret=%d\n",__FUNCTION__,ret);
    
    cout<<"the methed is :"<<n_count<<endl;
    return 0;
}