蓝桥杯 剪格子

问题描述如下图所示，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。输出格式输出一个整数，表示在所有解中，包含左上角的分割区可能包含的最小的格子数目。 样例输入13 310 1 5220 30 11 2 3 样例输出13 样例输入24 31 1 1 11 30 80 21 1 1 100 样例输出210 这个题我看了别人的做法，感觉很多人考虑都不太全面，这个题不仅要保证剪出那一块是总和的一半，还要保证分出的两块是连通的，所以从左上角开始搜索，当和为一半时判断没选中的剩下的是否连通，连通则更新答案。
#include<iostream>#include<cstring>using namespace std;int number_rest,m,n,ans,SUM,mat[10][10],used[10][10],vis[10][10],dir[4][2]={{-1, 0}, {1, 0}, {0, 1}, {0, -1}};void dfs_rest(int x,int y){	vis[x][y]=1;	number_rest++;//累加未选中的格子	for(int i=0;i<4;i++)      {      	int nx=dir[i][0]+x;      	int ny=dir[i][1]+y;	  if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && !used[nx][ny]&&!vis[nx][ny])	    dfs_rest(nx,ny);     }}void dfs_use(int x, int y,int number,int sum){	if(sum>SUM/2)  return;	if(sum==SUM/2)	{		memset(vis,0,sizeof(vis));		int i,j,ok=0;		for(i=1;i<=n;i++)		{		  for(j=1;j<=m;j++)		   if(!used[i][j])		   {		   	ok=1;		   break;}		   if(ok) break;    	}	number_rest=0;	dfs_rest(i,j);	if(number+number_rest==n*m)	ans=min(ans,number);	return;	}	for(int i=0;i<4;i++)	{	int nx = x + dir[i][0], ny = y + dir[i][1];		if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && !used[nx][ny])		{			used[nx][ny] = true;			sum += mat[nx][ny];            number=number+1;			dfs_use(nx, ny,number, sum);			used[nx][ny] = false;	//回溯，恢复原来状态			sum -= mat[nx][ny];			number=number-1;		}		}}int main(){	cin>>m>>n;	    ans = 0xFFFF;		for(int i = 1; i <= n; ++i)			for(int j = 1; j <= m; ++j)				cin >> mat[i][j],SUM+=mat[i][j];				used[1][1]=true;		if(SUM%2) 		cout<<0<<endl;		else		dfs_use(1, 1,1, mat[1][1]),		cout<< (ans!=0xFFFF ? ans : 0)<<endl;		return 0;}