当前位置: 首页 > >

蓝桥杯2013年JavaA题9(剪格子)

发布时间:

历届试题 剪格子



我们沿着图中的星号线剪开,得到两个部分,每个部分的数字和都是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


public class Main09 {
static int[][] g; //存放格子数值
static int[][] vis; //判断是否已经经过的标记
private static int n; //行
private static int m; //列
private static int total;
private static int ans = Integer.MAX_VALUE;

static void dfs(int i , int j, int steps, int sum){
if (i < 0 || i == n || j < 0 || j == m || vis[i][j]==1) return; //走出边界或者该点已经走过,非法路径
if (sum == total / 2){
ans=Math.min(ans,steps); //包含的最小的格子数目。
return;
}
if(sum>total/2) return; //相当于回溯

vis[i][j]=1; //标记经过路径
dfs(i-1,j,steps+1,sum + g[i][j]); //up
dfs(i+1,j,steps+1,sum + g[i][j]); //down
dfs(i,j-1,steps+1,sum + g[i][j]); //left
dfs(i,j+1,steps+1,sum + g[i][j]); //right
vis[i][j]=0; //剪枝
}
public static void main(String[] args){
// 程序先读入两个整数m n 用空格分隔(m,n<10)
//表示表格的宽度和高度
Scanner sc = new Scanner(System.in);
m = sc.nextInt();
n = sc.nextInt();
g = new int[n][m];
vis = new int[n][m];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
g[i][j]=sc.nextInt();
total = total + g[i][j];
}
}
// =完成输入=
dfs(0,0,0,0);
System.out.println(ans);
}


}


搜索??深度优先搜索(DFS)

设想我们现在身处一个巨大的迷宫中,我们只能自己想办法走出去,下面是一种看上去很盲目但实际上会很有效的方法。


以当前所在位置为起点,沿着一条路向前走,当碰到岔道口时,选择其中一个岔路前进。如果选择的这个岔路前方是一条死路,就退回到这个岔道口,选择另一个岔路前进。如果岔路口存在新的岔道口,那么仍然按上面的方法枚举新岔道口的每一条岔道。这样,只要迷宫存在出口,那么这个方法一定能够找到它。


也就是说,当碰到岔道口时,总是以“深度”作为前进的关键词,不碰到死胡同就不回头,因此这种搜索的方式称为深度优先搜索(DFS)。




友情链接: