这是一道dfs从左上角出发搜索所有的满足cnt = sum/2 的序列
剪枝：对于cnt > sum/2 的排序来说已经没有搜索的必要了 直接退回来就行了
注意是取最小值 ， 对于满足的序列需要比较一下深度
#include<iostream> #include<cstring> #include<algorithm> using namespace std ; const int N = 20 ; int a[N][N] ; int n , m ; int sum ,cnt; bool v[N][N] ; int d[4][2] = {{0,1},{0,-1},{1,0},{-1,0}} ; int ans = 100000 ; void dfs(int u,int x, int y){ if(cnt * 2 == sum){ if(u < ans ) ans = u ; return ; } if(cnt * 2 > sum) return ; for(int i = 0 ; i < 4 ; i ++){ int tx = x + d[i][0] , ty = y + d[i][1] ; if(tx < 0 || tx >= n || ty <0 || ty>=m) continue ; if(v[tx][ty]) continue ; v[tx][ty] = 1 ; cnt += a[tx][ty] ; dfs(u+1,tx,ty) ; v[tx][ty] = 0 ; cnt -= a[tx][ty] ; } } int main(){ cin >> n >> m ; for(int i = 0 ; i < m ; i ++){ for(int j = 0 ; j < n ; j ++){ cin >> a[i][j] ; sum += a[i][j] ; } } cnt = a[0][0] ; v[0][0] = 1 ; dfs(1,0,0); if(ans != 100000) cout << ans << endl; else cout << 0 << endl ; // int mid = sum / 2 ; if(sum%2!=0) cout << 0 << endl ; return 0 ; }
