试题 历届试题 剪格子（C++）

#include <iostream> using namespace std; const int INF = 1 << 30; int sum = 0; int m, n, a[15][15], ans; bool vis[15][15]; void dfs(int x, int y, int _sum, int _ans) { if (!a[x][y] || vis[x][y]) return ; _sum += a[x][y], ++_ans, vis[x][y] = true; /* 若还没出现和为一半的情况，ans == INF， 不可能出现 比ans大的 若出现了一种情况，那么 之后若 有 _ans > ans 无论能否组成都不考虑了 _sum > sum 比较好理解 就直接不合法了 */ if (_ans > ans || _sum > sum) {vis[x][y] = false; return ;} /* 能够到这一步的都是_ans <= ans 此时_sum == sum 直接替换一下ans 然后回溯就可以啦 */ if (_sum == sum) {ans = _ans; vis[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); vis[x][y] = false; } int main() { freopen("in.txt", "r", stdin); sum = 0; cin >> m >> n; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) { cin >> a[i][j]; sum += a[i][j]; } if (sum % 2 == 1) { cout << 0 << endl; system("pause"); } else { sum /= 2; ans = INF; dfs(1, 1, 0, 0); cout << (ans == INF ? 0 : ans); system("pause"); } return 0; }