蓝桥杯历届试题-剪格子 （C语言代码）

#include <stdio.h>
#define H 20000     //标记值
int m,n;
int map[10][10];   //图
int aim = 0;       //目标数值
int sum = 0;       //当前数值总和
int count = 0;     //当前步数
int min = 1<<30;   //记录最小步数
void dfs(int i, int j)     //深搜
{
    int tem = map[i][j];    //记录该点的值，用于回溯
    //如果该点在边界，并且不在两端，并且相邻的两个点都是没走过的，这步不能走，回退
    if ((i == 0 || i == m-1) && j > 0 && j < n-1 && map[i][j+1] != H && map[i][j-1] != H)
        return ;
    if ((j == 0 || j == n-1) && i > 0 && i < m-1 && map[i+1][j] != H && map[i-1][j] != H)
        return ;
    sum += tem;     //加数值
    count++;       //加步数
    if (sum == aim)    //如果是目标数值，更新最小值并回溯
    {
        min = count; 
        sum -= tem;
        count--;
        return ;
    }
    map[i][j] = H;      //标记
    if (count < min) 
    {
        //剪枝
        if (j < n-1 && map[i][j+1] != H && sum + map[i][j+1] <= aim)  
            dfs(i, j+1);
        if (j > 0 && map[i][j-1] != H && sum + map[i][j-1] <= aim)
            dfs(i, j-1);
        if (i < m-1 && map[i+1][j] !=H && sum + map[i+1][j] <= aim)
            dfs(i+1, j);
        if (i > 0 && map[i-1][j] != H && sum + map[i-1][j] <= aim)
            dfs(i-1 ,j);
    }
    //回溯
    sum -= tem;
    count--;
    map[i][j] = tem;
}
int main()
{
    int i, j;
    scanf("%d%d",&n,&m);
    for (i = 0; i < m; i++)
    {
        for (j = 0; j < n; j++)
        {
            scanf("%d",&map[i][j]);
            aim += map[i][j];
        }
    }
    if (aim % 2)    //如果总和是奇数则怎么都剪不了
    {
        printf("0");
        return 0;
    }
    aim /= 2;
    dfs(0, 0);
    if (min != 1<<30)      //如果最小值没被更新，则剪不了
        printf("%d",min);
    else 
        printf("0");
    return 0;
}

解题思路:





注意事项:





参考代码: