剪格子
time limit per test 1 second memory limit per test 256 megabytes
问题描述
如下图所示，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
3
样例输入2
4 3
1 1 1 1
1 30 80 2
1 1 1 100
样例输出2
10
题解
dfs要注意的地方还是挺多的，剪枝还有不越界
## AC code:(不包含输入类)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| import java.io.*;
import java.util.*;
public class Main {
static int[][]maze;
static int m;
static int n;
static int count;
static boolean flag;
static int sum;
static boolean[][]vis;
static int[]dx={1,-1,0,0};
static int[]dy={0,0,1,-1};
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
PrintWriter pw=new PrintWriter(System.out);
while(sc.hasNext()){
n=sc.nextInt();
m=sc.nextInt();
maze=new int[m][n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
maze[i][j]=sc.nextInt();
sum+=maze[i][j];
}
}
if(sum%2!=0){
pw.println(-1);
}
else{
vis=new boolean[m][n];
count=Integer.MAX_VALUE;
flag=false;
vis[0][0]=true;
dfs(0,0,0,1);
if(flag)pw.println(count);
else pw.println(-1);
}
pw.flush();
}
}
static boolean judge(int i,int j){
if(i<0||i>=m||j<0||j>=n) return false;
return true;
}
static void dfs(int i,int j,int s,int t){
if(s>sum/2) return;
if(t>=count) return;
if(s+maze[i][j]==sum/2){
count=Math.min(count,t);
flag=true;
return;
}
for(int q=0;q<4;q++){
int px=i+dx[q];
int py=j+dy[q];
if(judge(px,py)&&!vis[px][py]){
vis[px][py]=true;
dfs(px,py,s+maze[i][j],t+1);
vis[px][py]=false;
}
}
}
}
|
