试题历届试题剪格子（C++）

骑猪看日落 2022-12-11 15:18 192阅读 0赞

#include <iostream>
    
    using namespace std;
    const int INF = 1 << 30;
    int sum = 0;
    int m, n, a[15][15], ans;
    bool vis[15][15];
    
    void dfs(int x, int y, int _sum, int _ans)
    {
        
        if (!a[x][y] || vis[x][y]) return ;
        _sum += a[x][y], ++_ans, vis[x][y] = true;
        /*
            若还没出现和为一半的情况，ans == INF， 不可能出现 比ans大的
            若出现了一种情况，那么 之后若 有 _ans > ans 无论能否组成都不考虑了
            _sum > sum 比较好理解 就直接不合法了
        */
        if (_ans > ans || _sum > sum) {
        vis[x][y] = false; return ;}
        /*
            能够到这一步的都是_ans <= ans
            此时_sum == sum 直接替换一下ans
            然后回溯就可以啦
        */
        if (_sum == sum) {
        ans = _ans; vis[x][y] = 0; return ;}
        
        dfs(x - 1, y, _sum, _ans), dfs(x, y - 1, _sum, _ans);
        dfs(x + 1, y, _sum, _ans), dfs(x, y+1, _sum, _ans);
        vis[x][y] = false;
    }
    int main()
    {
        
        freopen("in.txt", "r", stdin);
        sum = 0;
        cin >> m >> n;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
            {
        
                cin >> a[i][j];
                sum += a[i][j];
            }
        if (sum % 2 == 1) 
        {
        
            cout << 0 << endl;
            system("pause");
        }
        else 
        {
        
            sum /= 2;
            ans = INF;
            dfs(1, 1, 0, 0);
            cout << (ans == INF ? 0 : ans);
            system("pause");
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，192人围观）

还没有评论，来说两句吧...

相关阅读

相关历届试题带分数

问题描述 100 可以表示为带分数的形式：100 = 3 + 69258 / 714。还可以表示为：100 = 82 + 3546 / 197。注意特征：带分数中，数

迈不过友情╰/ 2024年02月17日 19:24/ 0 赞/ 40 阅读

相关试题历届试题危险系数(c++)

思路：暴力枚举注意这是无向图，像我的代码里面，一条边要存两次 include <iostream> include <queue> inclu

柔光的暖阳◎/ 2022年12月13日 01:36/ 0 赞/ 169 阅读

相关试题历届试题剪格子（c++）

dfs（x, y, \_ans, \_sum）朝四个方向递归然后不行就回溯下面是两份代码，最下面那份带了注释，自行观看 include <iostream

柔光的暖阳◎/ 2022年12月12日 04:57/ 0 赞/ 212 阅读

相关试题历届试题大臣的旅费(c++)

代码是拷贝其他人的附链接：https://blog.csdn.net/the\_ZED/article/details/104174375?utm\_medium=dis

秒速五厘米/ 2022年12月12日 02:00/ 0 赞/ 141 阅读

相关试题历届试题错误票据(C++)

不清楚为什么超时，数据小的时候超时，怀疑是getchar的问题？ include <iostream> include <cstdio> includ

小咪咪/ 2022年12月11日 15:19/ 0 赞/ 173 阅读

相关试题历届试题剪格子（C++）

include <iostream> using namespace std; const int INF = 1 << 30; in

骑猪看日落/ 2022年12月11日 15:18/ 0 赞/ 193 阅读

相关历届试题剪格子

问题描述如下图所示，3 x 3 的格子中填写了一些整数。 \+--\--+--+ |10\ 1|52| \+--\\\\--+ |20|30\ 1| \\

心已赠人/ 2022年07月12日 08:22/ 0 赞/ 176 阅读

相关蓝桥杯历届试题带分数（简单搜索+剪支）

[题目链接][Link 1] 题意：给定一个数m，问用1-9这9个数，每个数只能出现一次，能组成多少种带分数且值等于m 思路：1-9每个数只能出现一次，很明显的全排列问题，

àì夳堔傛蜴生んèń/ 2022年03月19日 09:10/ 0 赞/ 227 阅读

相关历届试题剪格子

问题描述如下图所示，3 x 3 的格子中填写了一些整数。 ±-–±-+ |10 1|52| ±-\\\–+ |20|30 1| \\\\\\\–+

r囧r小猫/ 2022年03月06日 18:06/ 0 赞/ 205 阅读

相关历届试题带分数

问题描述 100 可以表示为带分数的形式：100 = 3 + 69258 / 714。还可以表示为：100 = 82 + 3546 / 197。注意特征：带分

Bertha 。/ 2022年03月06日 17:42/ 0 赞/ 229 阅读