【深度搜索】割绳子

点击量: 224 次

问题描述

如下图所示,3 x 3 的格子中填写了一些整数。
10    1    52
20    30    1
1    2    3
我们可以剪下10、20、30三个小块所连在一起的区域,得到两个部分,每个部分的数字和都是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

分析

遇到这种需要遍历所有可能性的当然要使用深度搜索(DFS)了~但是不能单纯的套用DFS模板,这个细节可能很难想到,因为这题和我们常见到的迷宫那种不需要返回初始点继续搜索的方式不同,请看以下例子。
2    2    2
2    3    1
2    4    2
假如地图是这样的,很明显map[0][0~2]map[0~2][0]构成了一个答案,如果按照普通DFS的话,我们从map[0][0]开始走到map[0][2],最后返回到map[0][0]的时候数据就会被清空。所以我们就需要一个特判,让尝试的时候返回原点继续让它搜索下去。当然上面这个例子的答案不是5,这里只是给大家做个演示。

AC代码

#include <iostream>
using namespace std;
int dir[2][4] = {{0, 1, 0, -1}, {1, 0, -1, 0}};                        //方向坐标
int m, n, map[10][10], book[10][10], sum=0, num=100;             
void dfs(int have, int i, int j, int step)                             //have是已搜集的数字,i,j是现在的位置,step是已走过的格子
{
    if(have==sum/2 && step<num)                                    //如果刚好数字达到一半且现在的步数少于记录的最小值,则更新它
    num = step;
    else                  
    for(int k=0; k<4; k++)                                         //尝试四个方向
    {
        int x = dir[0][k] + i;
        int y = dir[1][k] + j;
        if(book[x][y]==1 && i>=0 && i<n && j>=0 && j<m && (have+map[x][y]<=sum/2))        //如果可走
        {
            book[x][y] = 0;                                         //标记这个走过的位置
            if(x==0 && y==0)                                        //如果返回原点
            dfs(have, x, y, step);                                  //原点不需要再记录一次
            else
            dfs(have+map[x][y], x, y, step+1);                      //记录下这个没走过的位置,继续搜索
            book[x][y] = 1;                                         //取消标记便于下一次尝试
        }
    }
}
int main()
{
    cin>>m>>n;                                                     //注意是先录入纵坐标大小
    for(int i=0; i<n; i++)
    for(int j=0; j<m; j++)
    {
        cin>>map[i][j];
        sum += map[i][j];                                      //计算总大小
        book[i][j] = 1;                                        //提前标记可走
    }                                                                    
    if(sum%2==1)                                                   //如果为奇数则不可分
    cout<<0<<endl;
    else
    {
        dfs(map[0][0], 0, 0, 1);                               //开始尝试每一种可能性
        if(num!=100)                                           //如果能割(shan wu)
             cout<<num<<endl;
             else
             cout<<0<<endl;
    }
    return 0;
}
最大组合数 
下一篇:最大组合数


已有 8 条评论


  1. 援军
    援军

    pao.gif 大佬大佬!

     回复
    1. Kira
      Kira

      菜鸟菜鸟 wa.png

       回复
  2. waxxh
    waxxh

    哇,厉害 meng.png

     回复
    1. Kira
      Kira

      比你厉害多了 daxiao.png

       回复
  3. 芭比
    芭比

    虽然看不懂,但根据文采来说,是篇好文章

     回复
    1. Kira
      Kira

      彩虹屁吹的不错,给你奖励朵玫瑰 hua.png

       回复
  4. 鸟不拉屎
    鸟不拉屎

    C++我们大学的第一堂编程课 pao.gif
    每次上课都快睡着了

     回复
    1. Kira
      Kira

      睡啥睡,这么有意思的课 meng.png

       回复
点击开始摧毁这篇水文,方向键控制,空格发弹,Esc退出


pao.gifchui.gifpen.gifpai.gifhan.pngxia.pnghuaji.pngwa.pngbi.pngxin.pngleng.pnghua.pngmeng.pngjingya.pngqian.pnghan1.pngquan.pngnu.pnggan.pngdaxiao.pngku.pngqu.png



Proudly published with Typecho))).

Living (*>ω<*)

Copyright @ 2019 Kira's Blog



哎呀,穷死了,求赞赏!

支付宝
微信
QQ
0:00