【深度搜索】割绳子


问题描述

如下图所示,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;
}

声明:Kira's Blog|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 【深度搜索】割绳子


Truth is I missed those summer days