A2.

/* ======================== 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++; } } }

作者的说明：  //可惜只完成了一个

只交了一个题目，还有一个(A1)已到了90％了，但算了吧，时间很紧，就测试一个吧。

参赛人： mtnk@白云黄鹤

序号：   A5009