标题：剪格子
如图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
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意：不要使用package语句。不要使用jdk1.6及以上版本的特性。
注意：主类的名字必须是：Main，否则按无效代码处理。
解析：
首先理解题意，题目含义概述如下：
（1）有一个矩阵，矩阵中每个格子里面有一个数字，可以看成一个二维数组。
（2）在矩阵中进行裁剪分割，将矩阵分割成两个部分，两个部分的和相等，即每个部分都是总和的一半。
（3）分割之后符合两个部分和都相等的情况可能没有，可能有一种可能，也可能有多种可能。
（4）输出结果为符合分割之后两个部分都相等情况下，包含第一行第一列的部分格子的最小数量
思路：
（1）以第一行第一列格子为起点，利用递归（上下左右）四个方向进行移动联接，遍历所有的裁剪情况。
（2）在递归中进行格子上数字的累加，如果累加结果正好是所有数字之和的一半则符合裁剪条件。
（3）每次计算出符合裁剪条件的时候记录格子数量，并求最小值。
static int[][] arr; //二维数组保存格子每个元素的数据
static int[][] state; //二维数组标记每个格子是否已经走过1:走过,0:没有走过
static int m = 0; //二维数组的列
static int n = 0; //二维数组的行
static int sum = 0; //二维数组元素之和
static int min = 100; //假设符合条件的区块数量最小值(题目(m,n<10))
public static void move(int row,int col,int step,int add)
{
//判断当格子走出边界,或已经走过的格子,或累加之和已经超过所有数字之和的一半则退出
if(row < 0 || col <0 || row > n-1 || col > m-1 || state[row][col]==1 || add > sum/2)
return;
//判断
if(add == sum/2)
{
min = step < min ?step:min;
return;
}
state[row][col]=1; //标记该格子已经走过了
move(row-1,col,step+1,add+arr[row][col]); //上
move(row+1,col,step+1,add+arr[row][col]); //下
move(row,col-1,step+1,add+arr[row][col]); //左
move(row,col+1,step+1,add+arr[row][col]); //右
state[row][col]=0;//将标记进行还原
}
public static void main(String[] args) {
//用户输入
Scanner input = new Scanner(System.in);
m = input.nextInt();
n = input.nextInt();
arr = new int[n][m];
state = new int[n][m];
sum = 0;
for (int i = 0; i < arr.length; i++)
{
for (int j = 0; j < arr[i].length; j++) {
arr[i][j] = input.nextInt();
sum += arr[i][j];
}
}
//调用递归方法
move(0,0,0,0);
System.out.println(min==100?0:min); //如果无解则输出0
}
优化一：
上述代码只考虑了以第一行第一列格子为起点进行移动，但从第一行第一列格子为起点进行移动会漏掉一些裁剪情况，例如：
2 2
1 1
1 3
上述代码执行结果为0，但正确结果为3
或：
3 3
1 2 1
3 1 2
1 1 0
上述代码执行结果为4，但正确结果为3
所以不能只从第一行第一列格子为起点进行移动，需要以每个格子为起点进行移动，代码如下：
static int[][] arr; //二维数组保存格子每个元素的数据
static int[][] state; //二维数组标记每个格子是否已经走过1:走过,0:没有走过
static int m = 0; //二维数组的列
static int n = 0; //二维数组的行
static int sum = 0; //二维数组元素之和
static int min = 100; //假设符合条件的区块数量最小值(题目(m,n<10))
public static void move(int row,int col,int step,int add)
{
//判断当格子走出边界,或已经走过的格子,或累加之和已经超过所有数字之和的一半则退出
if(row < 0 || col <0 || row > n-1 || col > m-1 || state[row][col]==1 || add > sum/2)
return;
//判断累加的和正好等于总和一半，并且第一行第一列为已经走过的格子
if(add == sum/2 && state[0][0]==1)
{
min = step < min ?step:min;
return;
}
state[row][col]=1; //标记该格子已经走过了
move(row-1,col,step+1,add+arr[row][col]); //上
move(row+1,col,step+1,add+arr[row][col]); //下
move(row,col-1,step+1,add+arr[row][col]); //左
move(row,col+1,step+1,add+arr[row][col]); //右
state[row][col]=0;//将标记进行还原
}
public static void main(String[] args) {
//用户输入
Scanner input = new Scanner(System.in);
m = input.nextInt();
n = input.nextInt();
arr = new int[n][m];
state = new int[n][m];
sum = 0;
for (int i = 0; i < arr.length; i++)
{
for (int j = 0; j < arr[i].length; j++) {
arr[i][j] = input.nextInt();
sum += arr[i][j];
}
}
if(sum % 2 == 1) //如果奇数，直接打印结果
{
System.out.println(0);
return;
}
//从每个起点开始出发
for (int i = 0; i < arr.length; i++)
{
for (int j = 0; j < arr[i].length; j++) {
move(i,j,0,0);
}
}
//调用递归方法
System.out.println(min==100?0:min); //如果无解则输出0
}
优化二：
上述代码并没有考虑不包含第一行第一列的部分被切断的情况，如果被切断，则不符合题意，如下数据：
4 3
1 1 5 1
2 3 4 1
1 1 1 9
上述代码执行结果为5：
1 * 5 *
2 3 4 *
* * * *
但正确结果为6：
1 1 5 1
* 3 4 *
* * * *
所以在前面代码基础上添加函数判断被裁切另外一部分是否是联通的，通过此函数解决上述问题。
可以利用是否走过保存状态的数组进行判断，很容易想到判断每个0状态数字是否有上下左右同类，如果有一个0元素没有上下左右同类则表示图形被裁切数量>2，即
1 0 1 0
1 1 1 0
0 0 0 0
此种情况，第一行第二列的0元素上下左右找不到同类，则被裁切数量>2的，很好理解，算法设计也相对简单，但此思路是错误的，因为此思路无法求解如下情况：
1 0 0 1
1 1 1 1
0 0 0 0
上面的思路不行，我们更换思路，此时的思路为记录下任意一个为0元素的下标，让其自由行走，并不做重复的坐标不能走动的判断。
遇到0元素就改变其值为2并继续走，遇到1元素则停止，最后通过如下公式判断是否裁切为2部分：
裁切包含左上角的元素个数 + 状态为2的元素个数 != 元素总个数，则没有将图像裁切成2部分。
public static int[][] step = {{-1,0},{1,0},{0,-1},{0,1}};
static int[][] arr; //二维数组保存格子每个元素的数据
static int[][] state; //二维数组标记每个格子是否已经走过1:走过,0:没有走过
static int m = 0; //二维数组的列
static int n = 0; //二维数组的行
static int sum = 0; //二维数组元素之和
static int min = 100; //假设符合条件的区块数量最小值(题目(m,n<10))
//判断另外被裁切的另外一部分是否是联通的
public static void Check(int x, int y, int[][] v)
{
v[x][y] = 2;
for(int i = 0;i < 4;i++) {
int x1 = x + step[i][0];
int y1 = y + step[i][1];
if(x1 < 0 || x1 >= n || y1 < 0 || y1 >= m)
continue;
if(v[x1][y1] == 0)
Check(x1, y1, v);
}
}
public static void move(int row,int col,int step,int add)
{
//判断当格子走出边界,或已经走过的格子,或累加之和已经超过所有数字之和的一半则退出
if(row < 0 || col <0 || row > n-1 || col > m-1 || state[row][col]==1 || add > sum/2)
return;
//判断累加的和正好等于总和一半，并且第一行第一列为已经走过的格子
if(add == sum/2 && state[0][0]==1)
{
int x = 0, y = 0, step2 = 0;
int[][] v = new int[n][m];
for(int i = 0;i < n;i++) {
for(int j = 0;j < m;j++) {
if(state[i][j] == 0) {
x = i;
y = j;
}
v[i][j] = state[i][j];
}
}
Check(x, y, v);
for(int i = 0;i < n;i++)
for(int j = 0;j < m;j++)
if(v[i][j] == 2)
step2++;
//包含左上角的区域数量+未走过的区域数量如果不等于总数量,则没有裁切成2块
if(step2+step != n*m)
return;
min = step < min ?step:min;
return;
}
state[row][col]=1; //标记该格子已经走过了
move(row-1,col,step+1,add+arr[row][col]); //上
move(row+1,col,step+1,add+arr[row][col]); //下
move(row,col-1,step+1,add+arr[row][col]); //左
move(row,col+1,step+1,add+arr[row][col]); //右
state[row][col]=0;//将标记进行还原
}
public static void main(String[] args) {
//用户输入
Scanner input = new Scanner(System.in);
m = input.nextInt();
n = input.nextInt();
arr = new int[n][m];
state = new int[n][m];
sum = 0;
for (int i = 0; i < arr.length; i++)
{
for (int j = 0; j < arr[i].length; j++) {
arr[i][j] = input.nextInt();
sum += arr[i][j];
}
}
if(sum % 2 == 1) //如果奇数，直接打印结果
{
System.out.println(0);
return;
}
//从每个起点开始出发
for (int i = 0; i < arr.length; i++)
{
for (int j = 0; j < arr[i].length; j++) {
move(i,j,0,0);
}
}
//调用递归方法
System.out.println(min==100?0:min); //如果无解则输出0
}
