蓝桥杯.剪格子(DFS)

 Question:

Solve:

深搜板子题。分成两部分，两部分的数字和相同，dfs去创造路径，然后比对路径上的数字和与剩余点的数字和。

优化点

读入时候先求和sum，路径和ans另算，直接去判断ans是不是sum的一半

ans > sum/2之后不再可能出现成立的路径

Code:

#include <bits/stdc++.h>
using namespace std;
//sum原总和，ans:dfs所走路径的数字总和，cnt:dfs所走路径的点的个数，res:答案
int a[12][12], n, m, sum, ans, res, cnt;
int dir[4][2] = {1,0,-1,0,0,1,0,-1};  //四个方向
bool judge[12][12]; //判断每一个点是否走过
void dfs(int x, int y)
{
    //条件符合，选出最小的路径点数
    if(ans == sum/2) {
        res = min(res ,cnt);
        return ;
    }
    //ans>sum，之后ans一直加，sum一直减，不可能满足
    if(ans > sum/2) return ;
    //遍历四个方向
    for(int i = 0; i < 4; i++){
        int dx = x + dir[i][0];
        int dy = y + dir[i][1];
        //边界、点检测
        if(dx<=0 || dy<=0 || dx>n || dy>m || judge[dx][dy]==true) continue;
        cnt++; ans += a[dx][dy]; judge[dx][dy] = true;
        dfs(dx,dy);
        cnt--; ans -= a[dx][dy]; judge[dx][dy] = false;
    }
}
int main(void)
{
    memset(judge,false,sizeof(judge));
    sum = 0;
    cin >>m >> n;
    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
    {
        cin >>a[i][j];
        sum += a[i][j];
    }
    //初始化起始
    cnt = 1;  res = 110;
    ans = a[1][1];
    dfs(1,1);
    //输出结果res
    if(res == 110) cout <<0;
    else cout <<res;
    return 0;
}

声明:图片均来源于蓝桥杯官网，以个人刷题整理为目的，如若侵权，请联系删除~