题目描述
如图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
资源约定： 峰值内存消耗 < 64M CPU消耗 < 5000ms
思路分析
问题是可以变成路径问题，如果有解，那么找出一条从左上角开始的一条路径，这条路径的带权长度为总路径长度的一半。
采用深度优先遍历搜索，递归求解。
递归有两个问题需要解决，一个是什么时候return回去，一个是往哪里递归。
递归结束的条件一般是遇到边界返回，或者是找到解，这里存在最优解的情况，所以还需要记录每次解，将其和当前最优解进行比较。
方向是往上下左右递归，这里需要记得标记为已访问之后，回溯的时候需要取消标记，重新标记为未访问。然后距离和计数都退回上一步的状态。
AC代码
代码语言：javascript复制#include<iostream>
using namespace std;
int map[16][16];
int direction[4][2]={{0,1},{0,-1},{-1,0},{1,0}};
bool visited[16][16]={false};
int sum=0;
int answer=0,current=0,count=0;
int m,n;
const int OK=0;
const int ERROR=1;
int DFS(int x,int y){
if(x<0||y<0||x>=n||y>=m||visited[x][y])
return ERROR;
visited[x][y]= true;
current =map[x][y];
count ;
if(current*2==sum){
if(answer&&count>=answer)
return OK;
answer=count;
return OK;
}else if(current*2>sum)
return OK;
for(int i=0;i<4;i ){
if(DFS(x direction[i][0],y direction[i][1])==OK){
visited[x direction[i][0]][y direction[i][1]]=false;
current-=map[x direction[i][0]][y direction[i][1]];
count--;
}
}
return OK;
}
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];
}
DFS(0,0);
cout<<answer;
}
