a2.cpp

跳房子游戏

/*

  ========================
  A2.跳房子游戏
  ------------------------
  
	背景：
	小时候有玩过跳房子的游戏吗？就是那种在街道上用粉笔画出一些格子，然后在格子间跳
	来跳去（有时单脚，有时双脚）或是从格子中检起小石块。现在长大了，来点不一样的跳
	房子游戏吧！有一个n*n的格子矩阵，每个格子中放有0到100元不等的钱。参赛者一开始站
	在（0,0）的位置（也就是左上角的位置），他每次最多可以跳k格（当然，不能跳出格子
	矩阵外），横的方向或直的方向都可以。他每到一个格子，就把那格子中的钱收起来，但
	是有一个条件，就是他要跳的下一个格子中的钱一定要比现在所在的格子中的钱来的多。 
	
	  问题：
	  给你n, k以及各格子中的钱的大小，请你算出参赛者最多可以收集到多少钱。 
	  
		输入：
		输入的第一列有一个正整数，代表以下有多少组测试资料。每组测试资料的第一列有2个整
		数n,k（均介于1到100之间）。接下来的n列，每列有n个整数（均介于0到100之间），代表
		这n*n格子矩阵中每个格子里的钱。 
		输入的第一列与第一组测试资料之间，以及各组测试资料之间均有一空白列。
		
		  输出：
		  对于每一组测试资料输出一列，输出参赛者最多可以收集到多少钱。测试资料间亦请空一
		  列。 
		  
			输入样例：
			2
			
			  3 1
			  1 2 5
			  10 11 6
			  12 12 7
			  
				10 7
				21  40  96  33 100  57  63  56  99  71
				60  53  84  25  27  64  68  91  73  72
				36  83  52  97  39  82  83  28  80  89
				100  94  10  60  26  35   3   5 100 100
				41  97  97  84  37  84   7  24 100  81
				92  90 100  77  12  88  95  93  21  77
				100  94   4 100  98  90  31  58  35  23
				99  99  21  96  71  99  59  92  96   8
				7  34  56  99  77  18  46  96  85  91
				18  98  96  81  47  76  51  81  44  35
				
				  输出样例：
				  37
				  
					1436
*/


/*                  算法说明：

  穷举法，将所有符合规则的跳法均算一次   
  如果数据量较大  所需时间可能较长  。。。。。。
*/


#include <fstream>
#include <iostream>
using namespace std;

struct step
{
    int list[10001][2];   //跳法记录,  eg:   list[3][0]=4;list[3][1]=5;表示第三步是进入(4,5)格
	bool exist[101][101];  //表示某个格子是否进入过
	int TotalMoney;   //所有跳过的格里 总共的钱
	int p;  // 计数器  一共跳了几格
};	


//  定义全局变量:
int n;    //n*n格子矩阵
int k;    //每次最大跳的格子
int money[101][101];   //各格里的钱
int Final_Total_Money;   //最后希望所求的值
int leftm[101][101];  //比某个格子钱多的所有格子钱之和
int TotalMethod=0;
int percent_n;   // （用于统计计算进度）
int percent_total;      // percent_total 为第二步的跳法数，即从[1][1]跳有几种跳法  （用于统计计算进度）
int percent_temp0;  //（用于统计计算进度）
int percent_temp1;  //（用于统计计算进度）


//函数声明
void  WorkAllList(step)  ;   //生成所有可能跳法的函数,递归法
void  initialize_leftm();  // 根据 money[][]  初始化全局变量 leftm[][]
void  initialize_percent_total();  //初始化全局变量percent_total，（percent_total用于统计进度）


void main()
{
	cout<<"请将输入数据文件 hopscotch.in 放于本程序目录下";
	int i,j,i2;   //用于循环
	int test_num;  //   待测试的数据组数
    step start;  
	
	//文件操作
	ifstream indata;
	indata.open ("hopscotch.in");
	indata>>test_num;
	
	cout<<endl<<"OK";
	
	for(i2=1;i2<=test_num;i2++)
	{
		
		cout<<endl<<endl<<"第 "<<i2<<" 组数据:"<<endl;
		
		indata>>n;   
		indata>>k;   
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=n;j++)	indata>>money[i][j];
		}
		
		
		//初始化 start
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=n;j++)
			{
				start.exist[i][j]=0;
			}
		}
		start.p=1;
		start.TotalMoney=money[1][1];
		start.exist[1][1]=1;
		start.list[1][0]=1;
		start.list[1][1]=1;
		
		
		
		Final_Total_Money=0;     //不断记录所有算法中最大的MONEY，程序最后就输出它
		
		
		//初始化用于统计计算进度的全局变量
		percent_n=0;
		percent_temp0=0;
        percent_temp1=0;
		percent_total=0;
		
		
		initialize_leftm();  // 根据 money[][] 初始化全局变量 leftm[][]
		
		
		initialize_percent_total()	;    //初始化全局变量percent_total，（用于统计进度）
		
		WorkAllList(start);   // 調用函数
		
		cout<<endl<<"最后结果: "<<Final_Total_Money<<endl;  //显示最后结果
	}
	
	
	indata.close();  //关闭输入文件
	
	cin>>i;cin>>i;  //只是为了让程序输出答案后不立即自动关闭窗口 别无他意^_^
	
}


void  WorkAllList(step infun)     //生成所有可能跳法的函数,递归法
{   
	step newone;
	newone =infun;
	int endornot=0;
	int i;   //用于循环
    int x,y,newx,newy;
	x=infun.list[infun.p][0];
	y=infun.list[infun.p][1];
	
	if ( (infun.TotalMoney + leftm[x][y]) > Final_Total_Money )
	{
		
		for (i=1;i<=k;i++)
		{
			
			// 往上
			newone =infun;
			if (  (x-i)>=1    )  
			{   
				if  ( (infun.exist[x-i][y]==0)   &&   (money[x-i][y]>money[x][y])   )
				{
					endornot=1;
					newone.p++;
					newx=x-i;newy=y;
					newone.TotalMoney+=money[newx][newy];
					newone.exist[newx][newy]=1;
					newone.list[newone.p][0]=newx;newone.list[newone.p][1]=newy;
					WorkAllList(newone);
				}
			}
			
			
			//往下
			newone =infun;
			if (  (x+i)<=n  )   
			{   
				if (  (infun.exist[x+i][y]==0)   &&   (money[x+i][y]>money[x][y])   )
				{
					endornot=1;
					newone.p++;
					newx=x+i;newy=y;
					newone.TotalMoney+=money[newx][newy];
					newone.exist[newx][newy]=1;
					newone.list[newone.p][0]=newx;newone.list[newone.p][1]=newy;
					WorkAllList(newone);
				}
			}
			
			
			//往左
			newone =infun;
			if (  (y-i)>=1  )   
			{   
				if (    (infun.exist[x][y-i]==0)   &&   (money[x][y-i]>money[x][y])   )
				{
					endornot=1;
					newone.p++;
					newx=x;newy=y-i;
					newone.TotalMoney+=money[newx][newy];
					newone.exist[newx][newy]=1;
					newone.list[newone.p][0]=newx;newone.list[newone.p][1]=newy;
					WorkAllList(newone);
				}
			}
			
			
			
			//往右
			newone =infun;
			if (  (y+i)<=n  )   
			{   
				if (   (infun.exist[x][y+i]==0)   &&   (money[x][y+i]>money[x][y])   )
				{
					endornot=1;
					newone.p++;
					newx=x;newy=y+i;
					newone.TotalMoney+=money[newx][newy];
					newone.exist[newx][newy]=1;
					newone.list[newone.p][0]=newx;newone.list[newone.p][1]=newy;
					WorkAllList(newone);
				}
			}
			
		}
		if (endornot==0)
		{
			
			if ( infun.TotalMoney > Final_Total_Money )
			{
				Final_Total_Money=infun.TotalMoney; 
			}
			
			if   ( (  infun.list[2][0]!=percent_temp0 )  ||  (infun.list[2][1]!=percent_temp1 )  )
			{
				percent_n++;
				percent_temp0=infun.list [2][0];
				percent_temp1=infun.list[2][1];
			}
			
			
			
			cout<<"\r"<<"当前进度:"<<percent_n/percent_total*100<<"%"<<" ";
			cout<<"("<<percent_n<<" of "<<percent_total<<")";
			cout<<", 当前已算出的 Max Money: "<<Final_Total_Money<<"  计算中...  ";
		}
	}
}


void initialize_leftm()  //  根据 money[][]  初始化全局变量 leftm[][]
{
	//有待改进的一种方法：
	
	int i,j,o,q,r,s;  //用于循环
	int num=0;
	int temp;
	
	for (i=1;i<=n;i++)
	{
		for (j=1;j<=n;j++)
		{
			num=0;temp=0;
			for (o=1;o<=n;o++)
			{
				for(q=1;q<=n;q++)
				{
					if  (  money[o][q]>money[i][j] )  num+=money[o][q];
				}
			}
			leftm[i][j]=num;
			for (o=1;o<=n;o++)
			{
				for(q=1;q<=n;q++)
				{
					temp=0;  
					if (money[o][q]>money[i][j])
					{
						for (r=1;o<=n;o++)
						{
							for(s=1;q<=n;q++)
							{					       
								if (money[r][s]==money[o][q])  temp++;
							}
						}
						leftm[i][j]-=money[o][q]*(temp-1);
						
					}		  
				}
			}
			
		}
	}
	
	
}




void initialize_percent_total()  ////初始化全局变量percent_total，（percent_total用于统计进度）
{
    // percent_total 为第二步的跳法数，即从[1][1]跳有几种跳法  （用于统计计算进度）
	
	int i,j;
	
	for(j=2;j<=k+1;j++)
	{
		if ( money[1][j]>money[1][1] ) 
		{
			percent_total++;
		}
	}
	
	for(i=2;i<=k+1;i++)
	{
		if ( money[i][1] > money[1][1] )
		{
			percent_total++;
		}
	}
	
}