历届试题剪格子

问题描述

如下图所示，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 3
10 1 52
20 30 1
1 2 3

样例输出1

样例输入2

4 3
1 1 1 1
1 30 80 2
1 1 1 100

样例输出2

分析：看到这道题就应该想到DFS，并且题目给出数组的大小不大于10*10，所以基本不用担心超时的问题，我们可以考虑通过dfs找出所有的切割方法，保证整个大方格分为两块，且两块的数字之和大小相等，这时记录包含左上角的那个格子所在的一个

大格子含有多少个小格子，记录下来，和之后的情况的答案作对比，取最小值。先看一下我的版本一的代码：

 1 import java.util.Scanner;
 2     public class Main{   
 3         static int sum1=0;
 4         static int sum2=0;
 5         static int  sum=0;
 6         static int min=10000;
 7         static int m;
 8         static int n;
 9         static int array[][]=new int[10][10];
10         public static void main(String[] args) {
11             Scanner scanner=new Scanner(System.in);
12             m=scanner.nextInt();
13              n=scanner.nextInt();
14             for (int i = 0; i <n; i++) {
15                 for (int j = 0; j <= m; j++) {
16                     if(j==0) {
17                         array[i][j]=0;
18                         continue;
19                     }
20                     array[i][j]=scanner.nextInt();
21                 }
22             }
23             sum(0);
24             if(min==10000) {
25                 System.out.println(0);
26             }
27             else {
28                 System.out.println(min);
29             }
30             
31             
32         }
33         public static void sum(int a)
34         {
35             if(a==n) {
36                 //System.out.println(sum1+"----"+sum2);
37                 if(sum1==sum2) {
38                     if(sum<min) {
39                         min=sum;
40                     }
41                 }
42             }else {
43                 for (int i = 0; i <=m; i++) {
44                     sum2+=array[a][i];
45                 }
46                 int ss=sum1;
47                 for(int i=0;i<=m;i++) {
48                     sum1+=array[a][i];
49                     if(i!=0) sum++;
50                     sum2-=array[a][i];
51                     sum(a+1);
52                 }
53                 sum-=m;
54                 sum1=ss;
55             }
56         }
57     }
58

运行这个代码，我发现所给的测试用例答案都可以通过，可是系统给的测试用例通过不了，分析发现我的代码实现了每行所取的块都是连续的，即不能跳着取，比如下面的一种

1 1 1

1 8 1

1 1 1

我们可以把中间的8作为单独一块，外面的作为另一块，这样中间一行取的块是最左和最右的，跳过了中间的8，但是我的代码是每行从左到右取，所以出现了问题。

版本2的思路是仍然是dfs,不过是按着先右再上再左再下的步骤走这些格子，左上角的格子出发，一直向右走，把走过的路标记，到最顶端到达边界，再向上走，没路，向左，路已经走过，则向下，这样一直递归迭代下去，直到遇到走过的格子总和为所有格子的总数的一半，记录所包含的格子数，继续递归迭代，直到求得最小值解。

代码如下

 1 import java.util.Scanner;
 2     public class Main{   
 3         static int map[][]=new int[20][20];
 4         static int vis[][]=new int[20][20];
 5         static int dx[]= {1,0,-1,0};
 6         static int dy[]= {0,1,0,-1};
 7         static int m,n,s;
 8         static int min1=9999999;
 9         static int ans=1;
10     public static void main(String[] args) {
11         
12         Scanner scanner=new Scanner(System.in);
13          m=scanner.nextInt();
14          n=scanner.nextInt();
15         int sum1=0;
16         for (int i=0;i<n;i++)
17             for (int j=0;j<m;j++)
18             {
19                 map[i][j]=scanner.nextInt();
20                 sum1+=map[i][j];
21             }
22 
23         if (sum1%2!=0) 
24         System.out.println(0);
25         else if (sum1/2==map[0][0]) System.out.println(1);
26         else
27         {
28             s=sum1/2;
29             vis[0][0]=1;
30             dfsn(0,0,map[0][0]);
31             System.out.println(min1);
32         }
33         
34     }
35     static void dfsn(int x,int y,int sum)
36     {
37         if (sum==s)
38         {
39             if(ans<min1){
40                 min1=ans;
41             }
42         }
43         int i;
44         for (i=0;i<4;i++)
45         {
46             int nx=x+dx[i];
47             int ny=y+dy[i];
48             if (0<=nx && nx<n && 0<=ny && ny<m )
49             {
50                 if (sum+map[nx][ny]<=s && vis[nx][ny]!=1)
51 
52                 {
53                     vis[nx][ny]=1;
54                     ans++;
55                     int a=sum+map[nx][ny];
56                     dfsn(nx,ny,a);
57                     ans--;
58                     vis[nx][ny]=0;//初始化标志
59 
60                 }
61 
62             }
63 
64         }
65 
66     }
67    
68    }
69     
70   
71

历届试题 剪格子

推荐阅读

历届试题剪格子