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); }