美文网首页
蓝桥杯-剪格子【dfs】

蓝桥杯-剪格子【dfs】

作者: 黑夜里不灭的路灯 | 来源:发表于2019-02-27 21:39 被阅读0次

    标题:剪格子
    如图p1.jpg所示,3 x 3 的格子中填写了一些整数。
    我们沿着图中的红色线剪开,得到两个部分,每个部分的数字和都是60。
    本题的要求就是请你编程判定:对给定的m x n 的格子中的整数,是否可以分割为两个部分,使得这两个区域的数字和相等。
    如果存在多种解答,请输出包含左上角格子的那个区域包含的格子的最小数目。
    如果无法分割,则输出 0
    程序输入输出格式要求:
    程序先读入两个整数 m n 用空格分割 (m,n<10)
    表示表格的宽度和高度
    接下来是n行,每行m个正整数,用空格分开。每个整数不大于10000
    程序输出:在所有解中,包含左上角的分割区可能包含的最小的格子数目。

    例如:
    用户输入:
    3 3
    10 1 52
    20 30 1
    1 2 3

    则程序输出:
    3

    再例如:
    用户输入:
    4 3
    1 1 1 1
    1 30 80 2
    1 1 1 100

    则程序输出:
    10

    (参见p2.jpg)

    资源约定:
    峰值内存消耗 < 64M
    CPU消耗 < 5000ms

    请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。

    所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。

    注意: main函数需要返回0
    注意: 只使用ANSI C/ANSI C++ 标准,不要调用依赖于编译环境或操作系统的特殊函数。
    注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>, 不能通过工程设置而省略常用头文件。

    提交时,注意选择所期望的编译器类型。

    #include<bits/stdc++.h>
    using namespace std;
    int a[10][10];
    int dir[4][2]={0,1,1,0,0,-1,-1,0};
    int vis[10][10];
    int sum;
    int ans=0x7fffffff;
    int n,m;
    bool judge(int x,int y)
    {
        if(x<0||y<0||x>n-1||y>m-1)
            return false;
        if(vis[x][y])
            return false;
        return true;
    }
    
    void dfs(int x,int y,int num,int cnt)
    {
        if(num>sum/2)
            return ;
        if(num==sum/2)
        {
            ans=min(ans,cnt);
            return ;
        }
        for(int i=0;i<4;i++)
        {
            int xx=x+dir[i][0];
            int yy=y+dir[i][1];
            if(judge(xx,yy))
            {
                vis[xx][yy]=1;
                dfs(xx,yy,num+a[xx][yy],cnt+1);
                vis[xx][yy]=0;
            }
    
        }
    }
    int main()
    {
        scanf("%d%d",&m,&n);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                scanf("%d",&a[i][j]);
                sum+=a[i][j];
            }
        }
        vis[0][0]=1;
        dfs(0,0,a[0][0],1);
        printf("%d\n",ans);
    
    }
    

    相关文章

      网友评论

          本文标题:蓝桥杯-剪格子【dfs】

          本文链接:https://www.haomeiwen.com/subject/iapquqtx.html