算法1

用极值剪枝， 可行性剪枝了， 还优化了搜索顺序， 但最后一个数据还是TLE， 哭辽， 蹲个大佬吧先

时间复杂度 ~~

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;

const int N = 15;
int map[N][N];
bool st[N][N];
int n, m;
int res = 0x3fff;
int h;
int idx[4] = {-1, 0, 1, 0}, idy[4] = {0, 1, 0, -1};
int vt[N][N];
bool cons[N][N];
int getmax()
{
    int maxv = 0;
    int idx  = 0;
    for(int i = 0; i < m * n; ++ i)
        if(!cons[i / m][i % m] && map[i / m][i % m] > maxv)
            {
                maxv = map[i / m][i % m];
                idx = i;
            }
    return idx;
}

void flood(int i, int j)
{
    vt[i][j] = true;   
    for(int k = 0; k < 4; ++ k)
    {
        int x = i + idx[k], y = j + idy[k];    
        if(x < 0 || x >= n || y < 0 || y >= m) continue;
        if(vt[x][y]) continue;
        if(st[x][y] != st[i][j]) continue;
        flood(x, y);
    }
}

bool check()
{
    int cnt = 0;
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < m; ++ j)
            if(!vt[i][j])
            {
                flood(i, j);
                cnt ++;
            }
    if(cnt == 2)
        return true;
    return false;
}

void dfs(int sum, int cnt, int num, int left)
{
    if(sum > h) return;
    if(cnt >= res) return;
    if(left == 0) 
    {
        if(sum == h && check())
            res = cnt;
        memset(vt, 0, sizeof vt);
        return;
    }
    if(sum == h)
    {
        if(check())
           res = cnt;
        memset(vt, 0, sizeof vt);
        return;
    }
    cons[num / m][num % m] = true;
    st[num / m][num % m] = true;
    int maxidx = getmax();
    dfs(sum + map[num / m][num % m], cnt + 1, maxidx, left - 1);
    st[num / m][num % m] = false;
    dfs(sum, cnt, maxidx, left - 1);
    cons[num / m][num % m] = false;
}


int main()
{
    cin >> m >> n;
    int sum = 0;
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < m; ++ j)
            {
                cin >> map[i][j];
                sum += map[i][j];
            }
    h = sum / 2;
    if(sum != h * 2)
        cout << 0;
    else
    {
        st[0][0] = true;
        cons[0][0] = true;
        dfs(map[0][0], 1, getmax(), m * n - 1);
        if(res != 0x3fff)
            cout << res;
        else
            cout << 0;
    }
    return 0;
}