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

876 阅读 9 评论 0 点赞

原题链接：蓝桥杯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分

3 人评分

本文分类：题解列表
浏览次数：876 次浏览
发布日期：2020-09-24 11:28:59
本文链接：https://blog.dotcpp.com/a/72803

上一篇 > [编程入门]阶乘求和-题解（Java代码）
下一篇 > 同学的等待-题解（Java代码）

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表共有 9 条评论

王茂 3年前回复TA

你的程序只能检测能一笔走完的分区，但是不能一笔走完的正确区域却检测不出来啊
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吗）

王茂 3年前回复TA

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

差不多得了 3年前回复TA

剪枝写的不对

不知道叫啥 3年前回复TA

@呓语 按照题目的意思也是6啊

龚秋志 3年前回复TA

@呓语 对呀，按照道理来说输出的应该是7的，但我这个代码输出的是6。但竟然过了测试样例，说明有的情况测试样例没有给出来

呓语 4年前回复TA

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

龚秋志 4年前回复TA

@柳豪天 深搜

柳豪天 4年前回复TA

用的什么搜索啊大佬

三人丿木丶一兀之 4年前回复TA

大佬厉害厉害

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

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 9 条评论

发表评论 取消回复

评论列表共有 9 条评论

发表评论取消回复