洛谷P8601[蓝桥杯][2013年第四届真题]剪格子

题目描述

如图 11 所示，3×3 的格子中填写了一些整数。

我们沿着图中的红色线剪开，得到两个部分，每个部分的数字和都是 60。

本题的要求就是请你编程判定：对给定的 m×n 的格子中的整数，是否可以分割为两个部分，使得这两个区域的数字和相等。

如果存在多种解答，请输出包含左上角格子的那个区域包含的格子的最小数目。

如果无法分割，则输出 0。

输入格式

程序先读入两个整数m,n 用空格分割 (m,n<10)表示表格的宽度和高度。

接下来是 n 行，每行 m 个正整数，用空格分开。每个整数不大于10000。

输出格式

程序输出：在所有解中，包含左上角的分割区可能包含的最小的格子数目。

输入输出样例

输入

3 3

10 1 52

20 30 1

1 2 3

输出

3

输入

4 3

1 1 1 1

1 30 80 2

1 1 1 100

输出

10

说明/提示

第二个用例中：

时限 5 秒, 64M。蓝桥杯 2013 年第四届省赛

思路：利用搜索遍历每一种解决方案，把每种解决方案中格子的个数记录下来，然后输出最少格子数

#include<iostream>
using namespace std;
int g[11][11];
int vis[11][11];
int n, m, num[10010], sum, s, k;
int xx[] = { 1,0,-1,0 };
int yy[] = { 0,1,0,-1 };
void dfs(int x, int y)
{if (s == sum / 2){for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){if (vis[i][j] == 1) num[k]++;}}k++;return;}for (int i = 0; i < 4; i++){int dx = x + xx[i];int dy = y + yy[i];if (dx>=1 && dx<=n && dy>=1 && dy<=m && vis[dx][dy]==0 ){vis[dx][dy] = 1;s += g[dx][dy];dfs(dx, dy);s -= g[dx][dy]; //回溯vis[dx][dy] = 0;}}
}
int main()
{cin >> m >> n;int i, j;for (i = 1; i <= n; i++){for (j = 1; j <= m; j++){cin >> g[i][j];sum += g[i][j];}}vis[1][1] = 1;s += g[1][1];dfs(1, 1);int minn = num[0];for (i = 0; i < k; i++){minn = min(minn, num[i]);}cout << minn << endl;return 0;
}

这串代码在洛谷中只能跑过3个测试案例，暂时还没有找到更好的解决方法，呜呜~~