1462690283
摘要：本题是2013年第四届蓝桥杯全国软件大赛预赛A组第9题，编程题。
题目描述
标题：剪格子
如图p1.jpg所示，3 x 3 的格子中填写了一些整数。
我们沿着图中的红色线剪开，得到两个部分，每个部分的数字和都是60。
本题的要求就是请你编程判定：对给定的m x 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
资源约定
峰值内存消耗（含虚拟机） < 64M
CPU消耗 < 5000ms
解题思路
最简单最暴力的不过DFS，题目讲得很清楚，分成两个区域，求包含左上角格子的格子数，那么可以先求出平均值，然后从左上角开始遍历标记走过的位置然后加上当前的格子数值，不满足条件则回溯。
题目有毒，说是要输入m n，按正常人理解谁不是m行n列，后边看的时候才知道是n行m列，老毛病又犯哎，难怪我说第二个例子一直调试不出来。
代码实现
import java.util.Scanner;
/**
剪格子
@author Ape
/
public class DFS_4a9 {static int[][] map = new int[101][101];
static int[][] vis = new int[101][101];
static int[][] dir = new int[][] { { 1, 0 }, { 0, 1 }, { 0, -1 }, { -1, 0 } };
static int n, m, ans, num, pValue = 0;static void dfs(int x, int y, int value) {
if (x < 0 || y < 0 || x >= m || y >= n) return; if (value > pValue) return; if (value == pValue) { num = ans; return; } for (int i = 0; i < 4; i++) { int tx = x + dir[i][0]; int ty = y + dir[i][1]; if (tx < 0 || ty < 0 || tx >= m || ty >= n) continue; int tvalue = value + map[tx][ty]; if (vis[tx][ty] == 0 && tvalue <= pValue) { // 标记 vis[tx][ty] = 1; ans++; dfs(tx, ty, tvalue); // 回溯 ans--; vis[tx][ty] = 0; } }}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); m = scanner.nextInt(); for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) { map[i][j] = scanner.nextInt(); pValue += map[i][j]; } if (pValue % 2 == 1) // 若是奇数，输出0 System.out.println("0"); else { pValue = pValue / 2; // 从左上角开始 vis[0][0] = 1; ans = 1; dfs(0, 0, map[0][0]); System.out.println(num); } scanner.close();}
}