蓝桥杯：剪格子

剪格子     如图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

(参见p2.jpg)

import java.util.Scanner; public class Main { public static int n,m,gezi[][],state[][],min=100,c=0; public static void main(String[] args) { Scanner s=new Scanner(System.in); int sum=0; m=s.nextInt(); n=s.nextInt(); gezi=new int[n][m]; state=new int[n][m]; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ gezi[i][j]=s.nextInt(); sum+=gezi[i][j]; } } cut(0,0,sum/2); if(min==100) min=0; System.out.println(min); } public static int cut(int a,int b,int x){ if(x==0){ if(c<min){ min=c; } } if(x<0) return 100; if(a<n&&b<m&&a>=0&&b>=0){ if(state[a][b]==0){ x-=gezi[a][b]; state[a][b]=1; c++; cut(a+1,b,x); cut(a-1,b,x); cut(a,b+1,x); cut(a,b-1,x); // x+=gezi[a][b];//x为局部变量变不变回来 都一样 state[a][b]=0; c--; } } return min; } }