蓝桥杯2013年第四届真题-剪格子-题解（C语言代码）

#include <stdio.h>
int n,m,a[101][101],b[101][101],s,cou=1000;
int dx[4]={0,1,0,-1};	//左下上右四个方向 
int dy[4]={1,0,-1,0};
void dfs(int sum,int i,int j,int bs)
	{	int k;
		if(s==sum*2&&cou>bs)	//当sum为s 的一半，记录下块数 
			{
				cou=bs;
				return ;
			}
		else {
			for(k=0;k<4;k++)		//每个有四个方向可走 
				{
					int x=i+dx[k];
					int y=j+dy[k];
					if(b[x][y]==0&&x>=0&&y>=0&&x<n&&y<m&&(sum+a[x][y])<=s/2)	//在n*M数组内并且未被走过，加和小于s的一半 
						{
							b[x][y]=1;	//标记 
							dfs(sum+a[x][y],x,y,bs+1);//回溯，清除标记 
							b[x][y]=0;	
						}
				}
		}
	}
int main()
{	int i,j;
	scanf("%d%d",&m,&n);
	for(i=0;i<n;i++)
		for(j=0;j<m;j++)
			{
				scanf("%d",&a[i][j]);
				s+=a[i][j];
				b[i][j]=0;
			}
	if(s%2!=0)	//为奇数时肯定不能被分为两半 
		printf("0");
	else {
	dfs(a[0][0],0,0,1);
		if(cou==1000)	//无解 
			printf("0");
		else printf("%d",cou);	
	}
	
	return 0;
}