12.割地取田
先梳理这道题的过程:尝试这个矩阵的所有可行取法,然后选择其中sum最大的一种。
这道题应该属于回溯法的范畴,我使用了一个递归函数search,这个search本质上是一种dfs方法。
首先需要两个数组:vl[8][8](vl表示value,存放每个田地的预期产出)和av[8][8](av表示available,存放判断每个田地能否选择的数字,若为0则表示可以访问,若不为0则表示不能访问)
这里的size是8*8的原因是,我希望按照元素行列数(从1开始)而不是下标进行表示(从0开始),所以相比6,横竖都多留了一圈。
遍历逻辑:有一个当前访问位置(r,c),意为(row,column),这个位置从[1][1]开始遍历,逐行向右移动。若移动到一行末尾(c>M),则跳到下一行第一个位置。
每次移动当前位置会遇到两种情况:这个位置可以访问,则将位置的值vl[r][c]加到sum上,并将这个格子本身及其八邻域都加1表示禁止访问(通过操作av数组),访问位置向右移动两格(因为右边一格在当前格子的八邻域内,一定无法访问)。若不能,则向右移动一格。
返回条件:当一直逐行向右遍历到当前格子的行数大于总行数,即r>N时,停止遍历。把这个深度分支的sum与全局变量max比较,让max取较大的一个。返回,并将上一层的av恢复成1。
回溯:返回后,要将当前位置的八邻域恢复(减一),然后向右移动一格。(这个操作本质上是认为当前格子不能取。)
写了两个函数,tag和detag,分别负责把一个格子八邻域的可访问性加一或减一。
完整代码如下:
#include <stdio.h> int N,M; int max; int vl[8][8]; //vl for values int av[8][8]; //av for available void tag(int r,int c){ //标记 av[r-1][c-1]++; //左上 av[r-1][c]++; //上 av[r-1][c+1]++; //右上 av[r][c-1]++; //左 av[r][c]++; //自身 av[r][c+1]++; //右 av[r+1][c-1]++; //左下 av[r+1][c]++; //下 av[r+1][c+1]++; //右下 } void detag(int r,int c){ //去标记 //printf("detag\n"); av[r-1][c-1]--; //左上 av[r-1][c]--; //上 av[r-1][c+1]--; //右上 av[r][c-1]--; //左 av[r][c]--; //自身 av[r][c+1]--; //右 av[r+1][c-1]--; //左下 av[r+1][c]--; //下 av[r+1][c+1]--; //右下 } void print(){//使用这个函数打印每次递归的av矩阵。 int i,j; printf(" \n"); for(i=1;i<=N;i++){ for(j=1;j<=M;j++) printf("%d ",av[i][j]); //初始化 printf("\n"); } } void search(int r,int c,int sum){ //print(); //使用这个函数打印每次递归的av矩阵。 if(c>M){//遍历逻辑:逐行右移 r++; c=1; } if(r>N){//!!结束标志!! max= sum>max ? sum : max; return; } if(0==av[r][c]){//若该点可访问,更新sum,右移两格(右移一格肯定无法访问) tag(r,c); search(r,c+2,sum+vl[r][c]); detag(r,c); }//若不可访问或已回溯,不更新sum,右移一格。 search(r,c+1,sum); } int main(void){ max=0; scanf("%d %d",&N,&M); int i,j; for(i=1;i<=N;i++) for(j=1;j<=M;j++) scanf("%d",&vl[i][j]); for(i=0;i<8;i++) for(j=0;j<8;j++) av[i][j]=0; //初始化 search(1,1,0); printf("%d\n",max); }