蓝桥杯 翻硬币

#include <bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", x)
#define fi first
#define se second
#define eb emplace_back
#define endl '\n'
#define rep(i, j, k) for (ll(i) = (j); (i) <= (k); (++i))
#define rrep(i, j, k) for (ll i = (ll)(j); i >= (ll)(k); i--)
#define mem(x, y) memset(x, y, sizeof(x))
typedef long double ld;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
const ld pi = acos(-1);
const int mod = 1e9 + 7;
const ll INF = LLONG_MAX;
const int N = 1e2 + 7;
ll n, m, sum, a[N][N], ans = 1000;
ll dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bool vis[N][N], nvis[N][N];
int findt(int x, int y, int t) {
    int cnt = 0;
    if (x < 1 || x > n || y < 1 || y > m || nvis[x][y] || vis[x][y] != t)
        return 0;
    cnt++;
    nvis[x][y] = 1;
    rep(i, 0, 3) cnt += findt(x + dir[i][0], y + dir[i][1], t);
    return cnt;
}
bool chku() {
    // rep(i, 1, n) {
    //     rep(j, 1, m) cout << vis[i][j] << ' ';
    //     cout << endl;
    // }
    mem(nvis, 0);
    int cnt1 = findt(1, 1, 1);
    // cout << "cnt1=" << cnt1;
    mem(nvis, 0);
    rep(i, 1, n) rep(j, 1, m) if (!vis[i][j]) {
        int cnt2 = findt(i, j, 0);
        // cout << "   cnt2=" << cnt2 << endl;
        return cnt1 + cnt2 == n * m;
    }
    return 0;
}
void dfs(int x, int y, int num, int res) {
    if (x < 1 || x > n || y < 1 || y > m || vis[x][y] || res > sum)
        return;
    if (sum == res && chku()) {
        // cout << "YES" << endl;
        ans = min(ans, 1ll * num);
        return;
    }
    rep(i, 0, 3) {
        res += a[x][y], num++, vis[x][y] = 1;
        // cout << x << ' ' << y << endl;
        // cout << res << ' ' << num << ' ' << sum << endl;
        dfs(x + dir[i][0], y + dir[i][1], num, res);
        vis[x][y] = 0, num--, res -= a[x][y];
    }
}
int main() {
    cin >> m >> n;
    rep(i, 1, n) rep(j, 1, m) cin >> a[i][j], sum += a[i][j];
    if (!(sum & 1))
        sum /= 2;
    else
        cout << 0 << endl;
    // cout << sum << endl;
    if (a[1][1] <= sum)
        dfs(1, 1, 0, 0);
    if (ans == 1000)
        cout << 0 << endl;
    else
        cout << ans << endl;
    return 0;
}
/*

3 3
10 1 52
20 30 1
1 2 3

4 3
1 1 1 1
1 30 80 2
1 1 1 100

*/