c++深度优先搜素

#include<iostream>
using namespace std;
int m,n,cnt=0,sum=0,step=0,ans=9999999;
int dx[5]={0,-1,1,0,0};
int dy[5]={0,0,0,-1,1};
bool vis[15][15];
int a[15][15];
bool dfs(int x,int y,int sum,int step){
	
	if(x<0||y<0||x>n||y>m)
	{
		//ans=min(ans,step);
		return false;
	}
	if(sum==cnt/2){
		ans=min(ans,step);
	return true;	
	}
	for(int i=1;i<=4;i++){
		x+=dx[i];y+=dy[i];
		if(!vis[x][y]){
			vis[x][y]=1;
			sum+=a[x][y];
			dfs(x,y,sum,step+1);
			vis[x][y]=0;
			sum-=a[x][y];
		}
		x-=dx[i];y-=dy[i];
	}
}
int main(){
	cin>>m>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>a[i][j];
			cnt+=a[i][j];
		}
	}
	if(cnt%2!=0)cout<<0;
	else{
		if(dfs(0,0,a[0][0],1))
		cout<<ans;
	}
	
	return 0;
}

解题思路:

注意事项:

参考代码: