2013省赛---剪格子(递归深度搜索,)

2024-02-18 09:08

本文主要是介绍2013省赛---剪格子(递归深度搜索,),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

import java.util.Scanner;public class TestOne {static int[][] g;//输入的表格private static int n;//n行private static int m;//m列private static int minStep = Integer.MAX_VALUE; //存储最小格子数private static int total;//表格中的数据总和static int[][] vis;//访问标记。以访问的格子标记为1public static void main(String[] args) {Scanner sc = new Scanner(System.in);//1.输入行、列数(注意先输入列m)m = sc.nextInt();n = sc.nextInt();//2.输入表格中的数据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();//vis[i][j] = 0;total+=g[i][j];}}//3.对表格进行深度搜索,寻找满足条件的最少格子数dfs(0,0,0,0); //0行0列,已走格子数0,已走格子的累加和0//4.输出最小的步数System.out.println(minStep);}/*(1)对表格中的数据进行深度搜索*  (i,j):开始访问的格子坐标*  step:当前已访问的格子数目*  sum:当前已访问的格子累加和* */private static void dfs(int i, int j, int step, int sum) {//1. i、j越界 或者 当前格子已访问 (不合法)if(i<0 || i==n ||j<0 || j==m || vis[i][j]==1) return;//2. 已将表格划分为元素和相等的两部分if(sum==total/2) {minStep = Math.min(minStep, step);return;}//3. 超过总元素和一半 (不合法)if(sum>total/2) { return;}vis[i][j] = 1; //访问g[i][j]dfs(i-1,j,step+1,sum+g[i][j]);//上dfs(i+1,j,step+1,sum+g[i][j]);//下dfs(i,j-1,step+1,sum+g[i][j]);//左dfs(i,j+1,step+1,sum+g[i][j]);//右vis[i][j] = 0; //回溯}}

这篇关于2013省赛---剪格子(递归深度搜索,)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/720686

相关文章

Python使用DeepSeek进行联网搜索功能详解

《Python使用DeepSeek进行联网搜索功能详解》Python作为一种非常流行的编程语言,结合DeepSeek这一高性能的深度学习工具包,可以方便地处理各种深度学习任务,本文将介绍一下如何使用P... 目录一、环境准备与依赖安装二、DeepSeek简介三、联网搜索与数据集准备四、实践示例:图像分类1.

Redis 内存淘汰策略深度解析(最新推荐)

《Redis内存淘汰策略深度解析(最新推荐)》本文详细探讨了Redis的内存淘汰策略、实现原理、适用场景及最佳实践,介绍了八种内存淘汰策略,包括noeviction、LRU、LFU、TTL、Rand... 目录一、 内存淘汰策略概述二、内存淘汰策略详解2.1 ​noeviction(不淘汰)​2.2 ​LR

Python与DeepSeek的深度融合实战

《Python与DeepSeek的深度融合实战》Python作为最受欢迎的编程语言之一,以其简洁易读的语法、丰富的库和广泛的应用场景,成为了无数开发者的首选,而DeepSeek,作为人工智能领域的新星... 目录一、python与DeepSeek的结合优势二、模型训练1. 数据准备2. 模型架构与参数设置3

Rust中的BoxT之堆上的数据与递归类型详解

《Rust中的BoxT之堆上的数据与递归类型详解》本文介绍了Rust中的BoxT类型,包括其在堆与栈之间的内存分配,性能优势,以及如何利用BoxT来实现递归类型和处理大小未知类型,通过BoxT,Rus... 目录1. Box<T> 的基础知识1.1 堆与栈的分工1.2 性能优势2.1 递归类型的问题2.2

Java深度学习库DJL实现Python的NumPy方式

《Java深度学习库DJL实现Python的NumPy方式》本文介绍了DJL库的背景和基本功能,包括NDArray的创建、数学运算、数据获取和设置等,同时,还展示了如何使用NDArray进行数据预处理... 目录1 NDArray 的背景介绍1.1 架构2 JavaDJL使用2.1 安装DJL2.2 基本操

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动

Go中sync.Once源码的深度讲解

《Go中sync.Once源码的深度讲解》sync.Once是Go语言标准库中的一个同步原语,用于确保某个操作只执行一次,本文将从源码出发为大家详细介绍一下sync.Once的具体使用,x希望对大家有... 目录概念简单示例源码解读总结概念sync.Once是Go语言标准库中的一个同步原语,用于确保某个操

五大特性引领创新! 深度操作系统 deepin 25 Preview预览版发布

《五大特性引领创新!深度操作系统deepin25Preview预览版发布》今日,深度操作系统正式推出deepin25Preview版本,该版本集成了五大核心特性:磐石系统、全新DDE、Tr... 深度操作系统今日发布了 deepin 25 Preview,新版本囊括五大特性:磐石系统、全新 DDE、Tree

Node.js 中 http 模块的深度剖析与实战应用小结

《Node.js中http模块的深度剖析与实战应用小结》本文详细介绍了Node.js中的http模块,从创建HTTP服务器、处理请求与响应,到获取请求参数,每个环节都通过代码示例进行解析,旨在帮... 目录Node.js 中 http 模块的深度剖析与实战应用一、引言二、创建 HTTP 服务器:基石搭建(一

C# ComboBox下拉框实现搜索方式

《C#ComboBox下拉框实现搜索方式》文章介绍了如何在加载窗口时实现一个功能,并在ComboBox下拉框中添加键盘事件以实现搜索功能,由于数据不方便公开,作者表示理解并希望得到大家的指教... 目录C# ComboBox下拉框实现搜索步骤一步骤二步骤三总结C# ComboBox下拉框实现搜索步骤一这