本文共 1009 字，大约阅读时间需要 3 分钟。

题目：

问题描述

如下图所示，3 x 3 的格子中填写了一些整数。

+--*--+--+

|10* 1|52| +--****--+ |20|30* 1| *******--+ | 1| 2| 3| +--+--+--+

我们沿着图中的星号线剪开，得到两个部分，每个部分的数字和都是60。

本题的要求就是请你编程判定：对给定的m x n 的格子中的整数，是否可以分割为两个部分，使得这两个区域的数字和相等。

如果存在多种解答，请输出包含左上角格子的那个区域包含的格子的最小数目。

如果无法分割，则输出 0。

输入格式

程序先读入两个整数 m n 用空格分割 (m,n<10)。

表示表格的宽度和高度。

接下来是n行，每行m个正整数，用空格分开。每个整数不大于10000。

输出格式

输出一个整数，表示在所有解中，包含左上角的分割区可能包含的最小的格子数目。

样例输入1

3 3

10 1 52 20 30 1 1 2 3

样例输出1

3

样例输入2

4 3

1 1 1 1 1 30 80 2 1 1 1 100

样例输出2

10

思路：

dfs爆搜，剪枝的话超出一半的话就剪掉。

代码如下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;const int maxn=15;int n,m;int a[maxn][maxn];int ans=0x3f3f3f3f;int vis[maxn][maxn];int sum=0,ok=0;int loc[4][2]={
  {1,0},{-1,0},{0,1},{0,-1}};void dfs (int x,int y,int tsum,int ci){    if(tsum*2>sum) return;    if(tsum*2==sum)    {        ok=1;        ans=min(ans,ci);        return ;    }    for (int i=0;i<4;i++)    {        int tx=x+loc[i][0];        int ty=y+loc[i][1];        if(tx>=0&&tx
       
        =0&&ty
       
      
     
    
   

 

转载地址：http://szoen.baihongyu.com/