蓝桥杯 PREV-4 剪格子

题目链接：

PREV-4 剪格子

思路：

我们从左上角的格子开始dfs，途中记录sum和遍历的格子数，稍微剪枝即可；

代码：

#include<bits/stdc++.h>

using namespace std;

const int inf = 1 << 30;
int m, n, a[15][15], sum, ans;
bool vst[15][15];
void dfs(int x, int y, int _sum, int _ans) {
    if(!a[x][y] || vst[x][y]) return;
    _sum += a[x][y], ++_ans, vst[x][y] = true;
    if(_ans > ans || _sum > sum) { vst[x][y] = 0; return; }
    if(_sum == sum) { ans = _ans; vst[x][y] = 0; return; }
    dfs(x - 1, y, _sum, _ans), dfs(x, y - 1, _sum, _ans);
    dfs(x + 1, y, _sum, _ans), dfs(x, y + 1, _sum, _ans);
    vst[x][y] = 0;
}

int main() {
#ifdef MyTest
    freopen("Sakura.txt", "r", stdin);
#endif
    scanf("%d %d", &m, &n);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j]);
            sum += a[i][j];
        }
    if(sum & 1) { cout << 0; exit(0); }
    sum >>= 1;
    ans = inf;
    dfs(1, 1, 0, 0);
    cout << (ans == inf ? 0 : ans);
    return 0;   
}