龚秋志

用户名：uq_48078956563

访问量：55061

签　名：

等　　级
排　　名	36
经　　验	13978
参赛次数	30
文章发表	64
年　　龄	19
在职情况	学生
学　　校	湖北生物科技职业学院
专　　业	计算机应用

　　自我简介：

TA的其他文章

数据结构-图的遍历——BFS广度优先搜索-题解（Java代码）
浏览：303

发工资咯-题解（Java代码）
浏览：359

数据结构-图的遍历——DFS深度优先搜索-题解（Java代码）
浏览：400

你可能喜欢

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

蓝桥杯2013年第四届真题-剪格子-题解（Java代码）

　　作者: 龚秋志　　　　发表时间：2020-09-24 11:28:59 浏览：846　|　评论：6　

原题链接：蓝桥杯2013年第四届真题-剪格子

import java.awt.List;
    import java.util.ArrayList;
    import java.util.Scanner;

//测试样例有点小问题
	//3 3
	//1 1 1
	//1 1 1
	//1 2 5
	//这个按照题目的意思来说应该是 7  这套代码输出的是6 没想到测试样例竟然过了
    public class 剪格子 {
    
    	static int n, m;// 行数，列数
    	static int sum = 0;// 每个点的总数和
    	static boolean[][] isVisted;// 记录站点是否走过
    	static int[][] arr;// 邻接矩阵
    	static int ans = Integer.MAX_VALUE;// 最小裁剪格子数
    	static int[][] direction = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };// 方向
    
    	/**
    	 * 
    	 * @param x
    	 *            横坐标
    	 * @param y
    	 *            纵坐标
    	 * @param step
    	 *            剪过的格子数
    	 * @param hsum
    	 *            走过点的和
    	 */
    	public static void dfs(int x, int y, int step, int hsum) {
    		isVisted[x][y] = true;// 标记走过的点
    		hsum += arr[x][y];// 加上当前点的数
    		if (hsum == sum / 2) {// 表示已经剪好格子了
    			ans = Math.min(ans, step);// 取最小的格子数
    			return;
    		}
    		if (hsum > sum / 2) {// 剪枝 如果大于了一半说明后面就不可能会剪好了
    			return;
    		}
    		for (int i = 0; i < 4; i++) {// 试探方向
    			int x1 = x + direction[i][0];// 改变横坐标
    			int y1 = y + direction[i][1];// 改变纵坐标
    
    			// 判断是否越界 和是否走过
    			if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && !isVisted[x1][y1]) {
    				// 如果没有越界并且该点也没有走过则继续向下走
    				dfs(x1, y1, step + 1, hsum);
    				isVisted[x1][y1] = false;// 回溯
    			}
    		}
    	}
    
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		m = sc.nextInt();
    		n = sc.nextInt();
    		arr = new int[n][m];
    		isVisted = new boolean[n][m];
    
    		for (int i = 0; i < n; i++) {
    			for (int j = 0; j < m; j++) {
    				arr[i][j] = sc.nextInt();
    				sum += arr[i][j];// 求每个格子的总和
    			}
    		}
    
    		if (sum % 2 == 0) {
    			dfs(0, 0, 1, 0);
    			// 如果等于最大值则说明没有一种可能性被裁剪成功
    			if (ans == Integer.MAX_VALUE) {
    				System.out.println(0);
    			} else {
    				System.out.println(ans);
    			}
    			// 如果格子的总和不能是偶数 那么就不可能被裁剪成功
    		} else {
    			System.out.println(0);
    		}
    
    	}
    }

0.0分

4 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

王茂

你的程序只能检测能一笔走完的分区，但是不能一笔走完的正确区域却检测不出来啊
3 8
2 2 2 1 1 1 1 1
2 2 1 1 1 1 1 1
2 2 2 1 1 1 1 1
10（错误了，正确不应该是8吗）

2021-12-24 17:00:15

王茂

你怎么证明，分割的区域能够一笔走完？

2021-12-24 16:51:13

差不多得了

剪枝写的不对

2021-10-02 16:13:26

呓语

测试样例没错吧？ 第一列和第二列六个数是总数的一半 就可以通过啊

2021-01-18 14:06:15

柳豪天

用的什么搜索啊大佬

2020-10-08 09:16:07

三人丿木丶一兀之

大佬厉害厉害

2020-10-07 15:49:18

龚秋志

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C++代码）

C语言程序设计教程（第三版）课后习题6.2 （C++代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

蓝桥杯2013年第四届真题-剪格子-题解（Java代码）

评论区

精彩推荐

C二级辅导-同因查找（C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

分糖果（C++代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

WU-C语言程序设计教程（第三版）课后习题12.1 （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

愚蠢的摄影师（C++代码）

1014题解

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

龚秋志

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C++代码）

C语言程序设计教程（第三版）课后习题6.2 （C++代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

蓝桥杯2013年第四届真题-剪格子-题解（Java代码）

评论区

精彩推荐

C二级辅导-同因查找 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

分糖果 （C++代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

WU-C语言程序设计教程（第三版）课后习题12.1 （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

愚蠢的摄影师 （C++代码）

1014题解

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

　　评论区

C二级辅导-同因查找（C语言代码）

分糖果（C++代码）

愚蠢的摄影师（C++代码）