剪格子 （C++代码）（注释详细）

解题思路: 深度搜索+回溯筛选

注意事项:

参考代码:

#include<iostream>
using namespace std; 
int map[11][11];	//数表
int vis[11][11]={0};//标记访问数组初始化 
int df[4][2]={{0,-1},{1,0},{0,1},{-1,0}};
int m,n;			//边界值 
int minStep=100,sum=0;
void dfs(int s,int x,int y,int step){
	if(x>=1&&x<=m&&y>=1&&y<=n)	//检查是否在有效边界内 
		if(vis[x][y]==0){
			vis[x][y]=1;	//标记访问 
			s+=map[x][y];	
			if(s==sum) minStep=minStep>step?step:minStep;	//剪格子成功，统计最小步数（个数） 
			else if(s<sum)
			for(int i=0;i<4;i++)
					dfs(s,x+df[i][0],y+df[i][1],step+1);
			vis[x][y]=0;	//回溯到上一步（即要还原当前一步操作） 
		}
}
int main(){
	cin>>n>>m;	//注意题目给出的要求 先输宽，再输长 
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++){
			cin>>map[i][j];	
			sum+=map[i][j];	//求总和 
		}
	if(sum%2||(n==0&&m==0)){	//总和为奇数或者格子数为0  —无法分割 
		cout<<"0"<<endl; return 0;
	}
	if(map[1][1]==sum/2){		//一个格子就满足情况 
		cout<<"1"<<endl; 	return 0;
	} 
	sum/=2;	dfs(0,1,1,0);				
	if(minStep)cout<<minStep+1<<endl;	//最后得到格子数需要加上map[1][1]这个格子本身 
	else 	cout<<"0"<<endl;
	return 0;
}