lanqiaoOJ 211 剪格子

#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 ;
}