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

 

热门相关:总裁的秘密爱人   异能特工:军火皇后   上将大叔,狼来了!   嫡嫁千金   魔神狂后