剪格子(简单dfs)

#include<bits/stdc++.h>
using namespace std;
int m,n;   //行数和列数
int C=0;  //求矩阵和
int ans=1e9;   //保存结果
int vis[10][10];  //做标记，判断是否访问过了 
int arr[10][10]; //存放矩阵
void dfs(int i,int j,int count,int sum){
	if(sum==C/2){     //退出条件
		ans=min(ans,count);
		return;
	}
	if(sum>C/2) return;   //剪枝
	
	vis[i][j]=1;
	if(i+1<m&&vis[i+1][j]==0) dfs(i+1,j,count+1,sum+arr[i][j]);
	if(i-1>=0&&vis[i-1][j]==0) dfs(i-1,j,count+1,sum+arr[i][j]);
	if(j+1<n&&vis[i][j+1]==0) dfs(i,j+1,count+1,sum+arr[i][j]);
	if(j-1>=0&&vis[i][j-1]==0) dfs(i,j-1,count+1,sum+arr[i][j]);
	
	vis[i][j]=0;  //回溯
}


int main(){
	memset(vis,0,sizeof(vis));
	cin>>n>>m;
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			cin>>arr[i][j];
			C+=arr[i][j];
		}
	}
	dfs(0,0,0,0);
	if(ans==1e9){
		ans=0;
	}
	cout<<ans<<endl;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
 

文章来源: blog.csdn.net，作者：开心星人，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/qq_55675216/article/details/123966831