C++ 代码

#include <iostream>
#include<bits/stdc++.h>

using namespace std;
#define inf 0x3f3f3f3f

typedef long long ll;
typedef pair<int,int> P;

#define pi 3.141592653589793238


int mov[4][2]= {{-1,0},{0,1},{1,0},{0,-1}};
int M[13]={0,31,0,31,30,31,30,31,31,30,31,30,31};

int n,m;

bool vis[20][20];
set<string> S;
vector<P>   V;
int arr[20][20];
int sum;
int par[100];
int res;

int Find(int x){
    if(par[x]==x){
        return x;
    }else{
        return par[x]=Find(par[x]);
    }

}

bool check_con(int s){
    for(int i=0;i<m*n;i++){
        par[i]=i;
    }
    int cnt=m*n-s;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(!vis[i][j]){
                for(int k=0;k<4;k++){
                    int x=i+mov[k][0];
                    int y=j+mov[k][1];
                    if(x<0||x>=n||y<0||y>=m){
                        continue;
                    }
                    if(!vis[x][y]){
                        int F1=Find(x*m+y);
                        int F2=Find(i*m+j);
                        if(F1!=F2){
                            par[F1]=F2;
                            cnt--;
                        }
                    }
                }
            }
        }
    }
    return cnt==1;
}

bool exist(int N){
    string s(m*n,'0');
    for(int i=0;i<=N;i++){
        s[V[i].first*m+V[i].second]='1';
    }
    if(S.count(s)){
        return true;
    }
    S.insert(s);

    return false;
}

void dfs(int s,int step){
    if(s==sum/2){
        if(check_con(step)){
            res=step;
        }
        return;
    }
    vector<P> points;
    for(int i=0;i<step;i++){
        for(int k=0;k<4;k++){
            int xx=V[i].first+mov[k][0];
            int yy=V[i].second+mov[k][1];
            if(xx<0||xx>=n||yy<0||yy>=m){
                continue;
            }
            V[step].first=xx;
            V[step].second=yy;
            if(!vis[xx][yy]&&1+step<res&&s+arr[xx][yy]<=sum/2&&!exist(step)){
                points.push_back(P(xx,yy));
            }
        }
    }
    //sort(points.begin(),points.end());
    //points.erase(unique(points.begin(),points.end()),points.end());
    for(int i=0;i<points.size();i++){
        int x=points[i].first;
        int y=points[i].second;
        V[step].first=x;
        V[step].second=y;
        vis[x][y]=true;
        dfs(s+arr[x][y],step+1);
        vis[x][y]=false;
    }
}

int main()
{

    ios::sync_with_stdio(false);
    cin.tie(0);

    while(cin>>m>>n){
        res=200;
        V.resize(100);
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cin>>arr[i][j];
                sum+=arr[i][j];
            }
        }
        V[0].first=0;
        V[0].second=0;
        if(sum%2==0){
            vis[0][0]=true;
            dfs(arr[0][0],1);
            if(res==200){
                cout<<"0"<<endl;
            }else{
                cout<<res<<endl;
            }


        }else{
            cout<<"0"<<endl;
        }
    }

    return 0;
}