#include<bits/stdc++.h>
using namespace std;
int w[15][15], st[15][15], p[15 * 15], res, n, m, sum,
dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
unordered_set<long long> hash_table;
pair<int, int> cands[15 * 15];
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
bool check_connect(int k)
{
for(int i = 0; i < m * n; ++ i) p[i] = i;
int cnt = m * n - k;
for(int i = 0; i < n; ++ i)
for(int j = 0; j < m; ++ j)
if(!st[i][j])
{
for(int u = 0; u < 4; ++ u)
{
int a = i + dx[u], b = j + dy[u];
if(a < 0 || b < 0 || a >= n || b >= m) continue;
if(st[a][b]) continue;
int pa = find(i * m + j), pb = find(a * m + b);
if(pa != pb)
{
p[pa] = pb;
cnt --;
}
}
}
if(cnt == 1) return true;
return false;
}
bool check_exist(int k)
{
static pair<int, int> bk[15 * 15];
memcpy(bk, cands, sizeof cands);
sort(bk, bk + k);
long long x = 0;
for(int i = 0; i < k; ++ i)
{
x += x * 131 + bk[i].first + 1;
x += x * 131 + bk[i].second + 1;
}
if(hash_table.count(x)) return true;
hash_table.insert(x);
return false;
}
void dfs(int s, int k)
{
if(s == sum / 2)
{
if(check_connect(k))
res = min(res, k);
return;
}
vector<pair<int, int>> points;
for(int i = 0; i < k; ++ i)
for(int j = 0; j < 4; ++ j)
{
int x = cands[i].first, y = cands[i].second;
int a = x + dx[j], b = y + dy[j];
if(a < 0 || b < 0 || a >= n || b >= m) continue;
if(st[a][b]) continue;
cands[k] = {a, b};
if(k + 1 < res && !check_exist(k + 1) && (s + w[a][b] <= sum / 2))
points.push_back({a, b});
}
sort(points.begin(), points.end());
reverse(points.begin(), points.end());
for(int i = 0; i < points.size(); ++ i)
if(!i || points[i] != points[i - 1])
{
int a = points[i].first, b = points[i].second;
cands[k] = points[i];
st[a][b] = true;
dfs(s + w[a][b], k + 1);
st[a][b] = false;
}
}
int main()
{
cin>>m>>n;
for(int i = 0; i < n; ++ i)
for(int j = 0; j < m; ++ j)
{
cin>>w[i][j];
sum += w[i][j];
}
if(sum % 2 == 0)
{
cands[0] = {0, 0};
res = 1e8;
st[0][0] = true;
dfs(w[0][0], 1);
if(res == 1e8) cout<<0;
else cout<<res;
}
else cout<<0;
return 0;
}
好活,我还想的是不是要用状态压缩来做