历届试题 剪格子
时间限制：1.0s 内存限制：256.0MB
问题描述
如下图所示，3 x 3 的格子中填写了一些整数。
+–*–+–+|10* 1|52|+–****–+|20|30* 1|*******–+| 1| 2| 3|+–+–+–+
我们沿着图中的星号线剪开，得到两个部分，每个部分的数字和都是60。
本题的要求就是请你编程判定：对给定的m x n 的格子中的整数，是否可以分割为两个部分，使得这两个区域的数字和相等。
如果存在多种解答，请输出包含左上角格子的那个区域包含的格子的最小数目。
如果无法分割，则输出 0。
输入格式
程序先读入两个整数 m n 用空格分割 (m,n<10)。
表示表格的宽度和高度。
接下来是n行，每行m个正整数，用空格分开。每个整数不大于10000。
输出格式
输出一个整数，表示在所有解中，包含左上角的分割区可能包含的最小的格子数目。
样例输入1
3 310 1 5220 30 11 2 3
样例输出1
3
样例输入2
4 31 1 1 11 30 80 21 1 1 100
样例输出2
10
思想：（深搜+回溯） 最后实现全部遍历每种可能情况。
具体做法：从左上角开始搜索，按照 [上下左右] 的先后顺序。搜索过的点做上标记下次不再搜索（当回溯时，我们又去掉这个标记，使之下次还能被搜索）。
回溯有两种情况，第一种就是当某个点的上下左右都不满足时，回溯（退到上一步）。第二种情况就是当找到一种满足条件情况时，回溯。
其中注意，回溯时，我们需要记录当前情况剪掉的格子个数，以便于和下一次如果有多种情况比较，选出最小的剪格子数。
另外还有就是，回溯的时候，需要做3件事（即back()函数）：
1：将总和（sum）减去回溯掉的点。（因为你回退了一步，所以总和肯定不能有被回溯掉的那个点了）。
2：剪掉的格子数（count）-1。（假如：当前记录了你走了3步，意思就是剪掉3个格子，当你回退一步，你就只走了两步….所以…）
3：将标记重置（flag）。（因为你下次还要访问这个点，，不然你如何遍历全部?）
/*Name: 蓝桥杯 剪格子 Copyright: Analyst Author: Analyst Date: 05/03/14 15:31Description: dev-cpp 5.5.3*/#include <stdio.h>int m, n, half=0, sum = 0, minValue = 100, count = 0;int num[10][10]={0}, flag[10][10] = {0};int xzb[]={-1,1,0,0}; /*上下左右*/int yzb[]={0,0,-1,1};int isok(int x, int y) /*判断传入的坐标值是否能被选入*/{int yes = 0;/*不越界并且不超出和一半*/if ((x >= n || x < 0) || (y >= m || y < 0) || (flag[x][y] == 1) || (sum+num[x][y] > half))yes = 1; /*冲突*/return yes;}void back(int value, int x, int y) /*执行回退处理*/{–count;sum -= value;flag[x][y] = 0;}void dfs(int value, int x, int y) /*dfs搜索*/{int i, t1, t2;flag[x][y] = 1;/*标记为已走过*/++count;/*已走过点的个数*/sum += value;/*已走过的点的和*/if (sum == half){/*选出剪掉点数最少的方案*/minValue = minValue > count ? count : minValue;}else {for (i = 0; i < 4; ++i) /*按 上下左右 顺序遍历*/{t1 = x + xzb[i];/*引入t1,t2目的是使传入的x,y值不变，便于下面的回退*/t2 = y + yzb[i];if (isok(t1, t2) == 1)/*不可走*/continue;dfs(num[t1][t2], t1, t2);}}back(value, x, y); /*回退处理*/}int main(){int i, j, maxNum = 0, all = 0;scanf ("%d%d", &m, &n); for (i = 0; i < n; ++i)for (j = 0; j < m; ++j){scanf ("%d", &num[i][j]);all += num[i][j]; /*all为总和*/if (num[i][j] > maxNum) /*找出最大值*/maxNum = num[i][j];}if (all % 2 != 0 || maxNum > all / 2)/*如果和为基数或者最大值大于总和一半*/printf("0\n");else{half = all / 2;dfs(num[0][0], 0, 0);if (minValue != 100)/*找到*/printf("%d\n",minValue);elseprintf("0\n");}return 0;}
修正：感谢楼下nemoforif的指正。
我们先看一组数据：
2 2
1 1
1 3
正确的搜索结果应该是1 1 1 = 3。对于这组数据，上面的算法显然存在问题。因为上面的算法是按照上下左右的方式进行搜索的。
对于1 1 1 3这组数据，必须回溯到1（0.0）才能对右边的1（0,1）进行搜索。这样就将点1（1,0）回溯掉了。使问题找不到结果。
将问题抽象一下：
1 1 1 3这个例子就相当于上面中间的图，由于中间有一条线（就是中间的数据都很大，又不能选入，将两边数据隔开了，导致找不到结果）
对于这种情况我想了一个其他的解决方法：
小分析一下，看上面右边的图，出现1 1 1 3这种情况，则B,C两点肯定是要选进去的，所以我们可以从B或者C再搜索一次，而这样搜索就不会存在被挡住的现象了。
方案：我们进行两次搜索，起始点分别为A , B（A,C也可以），然后再选出合适的结果。
补充代码很简单：我们在主函数里面再调用一次dfs()函数就可以了。
说明：由于第二次是从（B点）开始搜索，当找到一组结果时，我们需要判断num[0][0]（左上角）的点有没有被选入。
/*Name: 蓝桥杯 剪格子 Copyright: Analyst Author: Analyst Date: 05/03/14 15:31Description: dev-cpp 5.5.3*/#include <stdio.h>int m, n, half=0, sum = 0, minValue = 100, count = 0, select = 1;int num[10][10]={0}, flag[10][10] = {0};int xzb[]={-1,1,0,0}; /*上下左右*/int yzb[]={0,0,-1,1};int isok(int x, int y) /*判断传入的坐标值是否能被选入*/{int yes = 0;/*不越界并且不超出和一半*/if ((x >= n || x < 0) || (y >= m || y < 0) || (flag[x][y] == 1) || (sum+num[x][y] > half))yes = 1; /*冲突*/return yes;}void back(int value, int x, int y) /*执行回退处理*/{if (x == 0 && y == 0)/*如果将num[0][0]回溯掉，则标记为未选入*/select = 0;–count;sum -= value;flag[x][y] = 0;}void dfs(int value, int x, int y) /*dfs搜索*/{int i, t1, t2;if (x == 0 && y == 0)/*主要用于B点开始的搜素，判断num[0][0]有没有被选入*/select = 1;flag[x][y] = 1;/*标记为已走过*/++count;/*已走过点的个数*/sum += value;/*已走过的点的和*/if (sum == half){if (select == 1)/*如果num[0，0]被选入，主要用于非[0，0]点开始的搜索*/minValue = minValue > count ? count : minValue; /*选出剪掉点数最少的方案*/}else {for (i = 0; i < 4; ++i) /*按 上下左右 顺序遍历*/{t1 = x + xzb[i];/*引入t1,t2目的是使传入的x,y值不变，便于下面的回退*/t2 = y + yzb[i];if (isok(t1, t2) == 1)/*不可走*/continue;dfs(num[t1][t2], t1, t2);}}back(value, x, y);/*如果上下左右都不可走：回退*/}int main(){int i, j, maxNum = 0, all = 0;scanf ("%d%d", &m, &n); for (i = 0; i < n; ++i)for (j = 0; j < m; ++j){scanf ("%d", &num[i][j]);all += num[i][j]; /*all为总和*/if (num[i][j] > maxNum) /*找出最大值*/maxNum = num[i][j];}if (all % 2 != 0 || maxNum > all / 2)/*如果和为基数或者最大值大于总和一半*/printf("0\n");else{half = all / 2;dfs(num[0][0], 0, 0);/*A点开始搜索*/if (n > 1)/*行数 > 1*/{select = 0;/*用于标记num[0][0]是否被选入 0：未选入。 1：选入*/dfs(num[1][0], 1, 0); /*选B点开始搜索*/}if (minValue != 100)/*找到*/printf("%d\n",minValue);elseprintf("0\n");}return 0;}
第三次修正，克服如下形式不能搜索到的问题：
不给自己一点轻松的机会，好象世界的每个角落都需要自己的脚去留个痕迹，才叫人生。
