我对于题目的一种理解
改造农场
1.建新农场 在空的点选
2.重建旧农场 选一个点属于这个农场的地方都要选

最后的农场都不能相连
所以枚举旧农场的个数并进行二分图匹配

#include<bits/stdc++.h>

using namespace std;

int N,M;

char mp[12][12];

vector<pair<int,int> > farm[12];

int has[12];

int dir[5][5] = { {1,0}, {0,1}, {-1,0}, {0,-1} };

int vis[12][12];

int ok(int x,int y) {

    if(x >= 1 && x <= N && y >= 1 && y <= M) return 1;

    else return 0;

}

int judge(int x, int y, int ty) {

    for(int i = 0; i < 4; ++i) {

        int t1 = x + dir[i][0]; int t2 = y + dir[i][1];

        if( ok(t1,t2) && mp[t1][t2] != '.' && mp[t1][t2] != ty+'0' && has[mp[t1][t2] - '0'] ) return 0;

        else if( ok(t1,t2) && mp[t1][t2] == '.' ) vis[t1][t2] = 1;

    }

    return 1;

}

int linker[12][12];

int used[12][12];

int dfs(int x, int y) {

    if( (x+y)%2 == 1 ) return 0;

//  printf("%d %d\n",x,y);

    for(int i = 0; i < 4; ++i) {

        int t1 = x + dir[i][0]; int t2 = y + dir[i][1];

        if( ok(t1,t2) && !used[t1][t2] && !vis[t1][t2]) {

            used[t1][t2] = 1;

            if( linker[t1][t2] == -1 || dfs(linker[t1][t2]/11, linker[t1][t2]%11) ) {

                linker[t1][t2] = x*11+y;

                return 1;

            }

        }

    }

    return 0;

}

int ccc = 0;

int main(){

    int T; scanf("%d",&T); int ca = 0;

    while(T--) {

        ccc = 0;

        scanf("%d %d",&N,&M);

        int ans = -1;

        for(int i = 0; i <= 10; ++i) farm[i].clear();

        for(int i = 1; i <= N; ++i) scanf("%s",mp[i]+1);

        for(int i = 1; i <= N; ++i) {

            for(int j = 1; j <= M; ++j) {

                if(mp[i][j] != '.') {

                    farm[mp[i][j] - '0'].push_back({i,j});

                }

            }

        }

        for(int i = 0; i < (1<<10); ++i) {

            int cc = 0;

            memset(has,0,sizeof(has));

            for(int j = 0; j < 10; ++j) {

                if( (i& (1<<j)) && (int)farm[j].size() ) {

                    has[j] ++; cc ++;

                }

            }

            if(!cc && i!=0) continue;

            memset(vis,0,sizeof(vis));

            int fl = 1;

            for(int j = 0; j < 10 && fl; ++j) {

                if(has[j]) {

                    for(int k = 0; k < (int)farm[j].size() && fl; ++k) {

                        fl = judge(farm[j][k].first, farm[j][k].second, j);

                    }

                }

            }

            if(!fl) continue;

            int tot = cc;

            for(int j = 1; j <= N; ++j)

                for(int k = 1; k <= M; ++k) {

                    if(mp[j][k] != '.') {

                        vis[j][k] = 1;

                    }else if(!vis[j][k]) tot ++;

                }

        /*

            if(ccc < 10) {

                for(int j = 0; j < 10; ++j) if(has[j]) printf("%d ",j); printf("\n");

                for(int j = 1; j <= N; ++j) {

                    for(int k = 1; k <= M; ++k) {

                        printf("%d ",vis[j][k]);

                    }

                    printf("\n");

                }

                ccc ++;

            }

            */

            int res = 0;

            memset(linker, -1, sizeof(linker));

            for(int j = 1; j <= N; ++j) {

                for(int k = 1; k <= M; ++k) {

                    if(vis[j][k]) continue;

                    memset(used,0,sizeof(used));

                    if(dfs(j,k)) res ++;

                }

            }

            ans = max(tot - res, ans);

        }

        printf("Case #%d: %d\n", ++ca,ans);

    }

    return 0;

}