当前位置: 首页 > news >正文

罗勇军 →《算法竞赛·快冲300题》每日一题:“游泳” ← DFS+剪枝

【题目来源】
http://oj.ecustacm.cn/problem.php?id=1753
http://oj.ecustacm.cn/viewnews.php?id=1023

【题目描述】
游泳池可以等分为n行n列的小区域,每个区域的温度不同。
小明现在在要从游泳池的左上角(1, 1)游到右下角(n, n),小明只能向上下左右四个方向游,不能游出泳池。
而小明对温度十分敏感,他希望你帮他找一条最舒适的路径,使路径上的
最高的水温和最低的水温差值最小。

【输入格式】
第一行输入一个正整数n。
接下来n行,每行n个正整数,表示方阵每个区域的温度a[i][j]。
所有数据保证随机。
(1≤n≤100,1≤a[i][j]≤1000)

【输入格式】
一行一个数表示最小差值。

【输入样例】
4
1 3 10 8
1 4 10 8
1 1 1 1
1 5 8 8

【输出样例】
7

【算法分析】
由于本题规定小明可以往上下左右四个方向游,也就是说可以走回头路,所以不能用动态规划。故依据本题题意,若要找一条最舒适的路径的话,就需要用搜索算法了。
但是,如果简单地遍历出所有路径,再比较得到温差最小路径,肯定超时,必须
剪枝才能减少路径的搜索数量。
如何剪枝?这是本题难点。因为,如果已知最小温差,只需一边游一边检查当前路径上的最大温差,如果已经超过了允许的最小温差,就不用走下去了。但是,
最小温差不能预知,只能猜。最好的方法是使用二分法来猜这个最小温差。本题的解法是“DFS+二分法”。 用“BFS+二分法”也行,请大家思考。

【算法代码】

#include<bits/stdc++.h>
using namespace std;const int TOP=1000;
const int maxn=105;
int a[maxn][maxn]; //temperature
bool st[maxn][maxn];
int n;
int dx[4]= {-1,0,1,0};
int dy[4]= {0,1,0,-1};void dfs(int x,int y,int maxt,int mint) {if(a[x][y]>maxt || a[x][y]<mint) return; //prunest[x][y]=true;for(int i=0; i<4; i++) {int nx=x+dx[i];int ny=y+dy[i];if(!st[nx][ny] && nx>=1 && nx<=n && ny>=1 && ny<=n)dfs(nx,ny,maxt,mint);}
}bool check(int x) {for(int i=1; i+x<=TOP; i++) {memset(st,0,sizeof(st));dfs(1,1,i+x,i);if(st[n][n]) return 1;}return 0;
}int main() {scanf("%d",&n);for(int i=1; i<=n; i++) {for(int j=1; j<=n; j++) {scanf("%d",&a[i][j]);}}int le=1,ri=TOP;while(le<=ri) {int mid=(le+ri)/2;if(check(mid)) ri=mid-1;else le=mid+1;}printf("%d",ri+1);return 0;
}/*
in:
4
1 3 10 8
1 4 10 8
1 1 1 1
1 5 8 8out:
7
*/





【参考文献】
https://blog.csdn.net/weixin_43914593/article/details/131912564


 

相关文章:

罗勇军 →《算法竞赛·快冲300题》每日一题:“游泳” ← DFS+剪枝

【题目来源】http://oj.ecustacm.cn/problem.php?id1753http://oj.ecustacm.cn/viewnews.php?id1023【题目描述】 游泳池可以等分为n行n列的小区域&#xff0c;每个区域的温度不同。 小明现在在要从游泳池的左上角(1, 1)游到右下角(n, n)&#xff0c;小明只能向上下左右四个方…...

【教程】PyTorch Timer计时器

转载请注明出处&#xff1a;小锋学长生活大爆炸[xfxuezhang.cn] OpenCV的Timer计时器可以看这篇&#xff1a;Python Timer和TimerFPS计时工具类 Timer作用说明&#xff1a;统计某一段代码的运行耗时。 直接上代码&#xff0c;开箱即用。 import time import torch import os …...

因果推断(六)基于微软框架dowhy的因果推断

因果推断&#xff08;六&#xff09;基于微软框架dowhy的因果推断 DoWhy 基于因果推断的两大框架构建&#xff1a;「图模型」与「潜在结果模型」。具体来说&#xff0c;其使用基于图的准则与 do-积分来对假设进行建模并识别出非参数化的因果效应&#xff1b;而在估计阶段则主要…...

探索隧道ip如何助力爬虫应用

在数据驱动的世界中&#xff0c;网络爬虫已成为获取大量信息的重要工具。然而&#xff0c;爬虫在抓取数据时可能会遇到一些挑战&#xff0c;如IP封禁、访问限制等。隧道ip&#xff08;TunnelingProxy&#xff09;作为一种强大的解决方案&#xff0c;可以帮助爬虫应用更高效地获…...

题目:2629.复合函数

​​题目来源&#xff1a; leetcode题目&#xff0c;网址&#xff1a;2629. 复合函数 - 力扣&#xff08;LeetCode&#xff09; 解题思路&#xff1a; 倒序遍历计算。 解题代码&#xff1a; /*** param {Function[]} functions* return {Function}*/ var compose function(…...

【实训项目】精点考研

1.设计摘要 如果说高考是一次能够改变命运的考试&#xff0c;那么考研应该是另外一次。为什么那么多人都要考研呢&#xff1f;从中国教育在线官方公布是考研动机调查来看&#xff0c;大家扎堆考研的原因大概集中在这6个方面&#xff1a;本科就业压力大&#xff0c;提升竞争力、…...

软件测试Pytest实现接口自动化应该如何在用例执行后打印日志到日志目录生成日志文件?

Pytest可以使用内置的logging模块来实现接口自动化测试用例执行后打印日志到日志目录以生成日志文件。以下是实现步骤&#xff1a; 1、在pytest配置文件&#xff08;conftest.py&#xff09;中&#xff0c;定义一个日志输出路径&#xff0c;并设置logging模块。 import loggi…...

深入理解作用域、作用域链和闭包

​ &#x1f3ac; 岸边的风&#xff1a;个人主页 &#x1f525; 个人专栏 :《 VUE 》 《 javaScript 》 ⛺️ 生活的理想&#xff0c;就是为了理想的生活 ! ​ 目录 &#x1f4da; 前言 &#x1f4d8; 1. 词法作用域 &#x1f4d6; 1.2 示例 &#x1f4d6; 1.3 词法作用域的…...

7款适合3D建模和渲染的GPU推荐

选择一款完美的 GPU 并不是一件容易的事&#xff1b;您不仅必须确保有特定数量的线程和内核来处理图像&#xff0c;而且还应该有足够的 RAM。 这是因为 3D 渲染是一个活跃的工作过程&#xff0c;因为您必须坐在 PC 前并持续与软件交互。为了在 3D 场景中积极工作&#xff0c;您…...

边缘计算物联网网关在机械加工行业的应用及作用分享

随着工业4.0的推进&#xff0c;物联网技术正在逐渐渗透到各个行业领域。机械加工行业作为制造业的基础领域之一&#xff0c;其生产过程的自动化、智能化水平直接影响到产品质量和生产效率。边缘计算物联网网关作为物联网技术的重要组成部分&#xff0c;在机械加工行业中发挥着越…...

(笔记六)利用opencv进行图像滤波

&#xff08;1&#xff09;自定义卷积核图像滤波 import numpy as np import matplotlib.pyplot as plt import cv2 as cvimg_path r"D:\data\test6-6.png" img cv.imread(img_path)# 图像滤波 ker np.ones((6, 6), np.float32)/36 # 构建滤波器&#xff08;卷积…...

WPF C# .NET7 基础学习

学习视频地址&#xff1a;https://www.bilibili.com/video/BV1hx4y1G7C6?p3&vd_source986db470823ebc16fe0b3d235addf050 开发工具&#xff1a;Visual Studio 2022 Community 基础框架&#xff1a;.Net 6.0 下载创建过程略 .Net和.Framework 区别是Net是依赖项&#xff…...

QT里使用sqlite的问题,好多坑

1. 我使用sqlite&#xff0c;开发机上好好的&#xff0c;测试机上却不行。后来发现是缺少驱动&#xff08;Driver not loaded Driver not loaded&#xff09;&#xff0c;代码检查了又检查&#xff0c;发现应该是缺少dll文件&#xff08;系统不提示&#xff0c;是自己使用 QMes…...

openGauss学习笔记-59 openGauss 数据库管理-相关概念介绍

文章目录 openGauss学习笔记-59 openGauss 数据库管理-相关概念介绍59.1 数据库59.2 表空间59.3 模式59.4 用户和角色59.5 事务管理 openGauss学习笔记-59 openGauss 数据库管理-相关概念介绍 59.1 数据库 数据库用于管理各类数据对象&#xff0c;与其他数据库隔离。创建数据…...

Nginx安装与部署

文章目录 一,说明二,下载三,Windows下安装1,安装2,启动3,验证 四,Linux下安装1,安装2,启动3,验证 五,Nginx配置 一,说明 Nginx是一款高性能Web和反向代理服务器,提供内存少,高并发,负载均衡和反向代理服务,支持windos和linux系统 二,下载 打开浏览器,输入地址: https://ngin…...

Linux中Tomcat发布war包后无法正常访问非静态资源

事故现象 在CentOS8中安装完WEB环境&#xff0c;首次部署WEB项目DEMO案例&#xff0c;发现可以静态的网页内容&#xff0c; 但是无法向后台发送异步请求&#xff0c;全部出现404问题&#xff0c;导致数据库数据无法渲染到界面上。 原因分析 CentOS请求中提示用来获取资源的连…...

大数据、AI和云原生:引领未来软件开发的技术演进

文章目录 **1. 数据驱动的创新&#xff1a;****2. 智能化应用的兴起&#xff1a;****3. 云原生的敏捷和可扩展性&#xff1a;****4. 实时性和即时性&#xff1a;****5. 数据隐私和安全&#xff1a;****6. 跨平台和跨设备&#xff1a;****7. 自动化和智能编程&#xff1a;****8.…...

Text-to-SQL小白入门(四)指令进化大模型WizardLM

摘要 本文主要对大模型WizardLM的基本信息进行了简单介绍&#xff0c;展示了WizardLM取得的优秀性能&#xff0c;分析了论文的核心——指令进化方法。 论文概述 基本信息 英文标题&#xff1a;WizardLM: Empowering Large Language Models to Follow Complex Instructions中…...

浅谈红队资产信息收集经验

文章目录 子公司资产收集备案号|官网收集子域名|ip收集fofa灯塔ARLX情报社区 资产确认目录扫描Google Hacking绕过CDNnmap端口扫描参数技巧其他常用工具 子公司资产收集 红蓝对抗中往往只会给你目标企业的名称&#xff0c;以及对应的靶标系统地址&#xff0c;而很少有直接从靶标…...

list根据对象中某个字段属性去重Java流实现

list根据对象中某个字段属性去重Java流实现&#xff1f; 在Java的流(Stream)中&#xff0c;你可以使用distinct方法来实现根据对象中某个字段属性去重的功能。要实现这个功能&#xff0c;你需要重写对象的hashCode和equals方法&#xff0c;以确保相同字段属性的对象被认为是相…...

软件架构设计(三) B/S架构风格-层次架构(一)

层次架构风格从之前的两层C/S到三层C/S,然后演化为三层B/S架构,三层B/S架构之后仍然在往后面演化,我们来看一下层次架构演化过程中都有了哪些演化的架构风格呢? 而我们先简单了解一下之前的层次架构风格中分层的各个层次的作用。 表现层:由于用户进行交互,比如MVC,MVP,…...

大端字节和小端字节

介绍 大端字节序&#xff08;Big-Endian&#xff09;和小端字节序&#xff08;Little-Endian&#xff09;是在计算机系统中用来表示多字节数据类型&#xff08;如整数、浮点数等&#xff09;的存储方式。字节序指的是在内存中多字节数据的存放顺序&#xff0c;即哪个字节在前&…...

(10)(10.8) 固件下载

文章目录 ​​​​​​​前言 10.8.1 固件 10.8.2 Bootloader 10.8.3 APM2.x Autopilot 10.8.4 许可证 10.8.5 安全 前言 固件服务器(firmware server)可提供所有飞行器的最新固件。其中包括&#xff1a; CopterPlaneRoverAntennaTrackerSub 本页提供了一些被视为&quo…...

vue实现列表自动滚动效果

效果如图&#xff1a; 1.下载插件 npm install vue-seamless-scroll --save 2.在main.js中引入注册 import scroll from vue-seamless-scroll Vue.use(scroll) 3.在页面中使用&#xff08;写一个固定的表头 el-table:show-header"status" 设置为false,自带的表头不…...

如何通过构建遥感光谱反射信号与地表参数之间的关系模型来准确估算植被参数?植被参数光学遥感反演方法(Python)及遥感与生态模型数据同化算法

目录 专题一 植被参数遥感反演理论 专题二 植被叶片及冠层反射率模拟与处理 专题三 植被遥感模型参数敏感性分析 专题四 基于查找表(LUT)方法反演植被参数 专题五 基于优化算法反演植被参数 专题六 基于机器学习反演植被参数 专题七 遥感数据同化理论 专题八 同化遥感反…...

持续集成与持续交付(CI/CD):探讨在云计算中实现快速软件交付的最佳实践

文章目录 持续集成&#xff08;CI&#xff09;的最佳实践持续交付&#xff08;CD&#xff09;的最佳实践云计算环境下的特别注意事项 &#x1f388;个人主页&#xff1a;程序员 小侯 &#x1f390;CSDN新晋作者 &#x1f389;欢迎 &#x1f44d;点赞✍评论⭐收藏 ✨收录专栏&am…...

【LeetCode题目详解】第九章 动态规划part02 62.不同路径 63. 不同路径 II day39补

本文章代码以c为例&#xff01; 一、力扣第62题&#xff1a;不同路径 题目&#xff1a; 一个机器人位于一个 m x n 网格的左上角 &#xff08;起始点在下图中标记为 “Start” &#xff09;。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角&#xff08;…...

四维轻云助力在线管理、展示及分享多种地理空间数据

《四维轻云》是一款轻量化的地理空间数据管理云平台&#xff0c;支持倾斜摄影模型、激光点云、数字高程模型及正射影像等多种地理空间数据的在线管理、展示及分享。目前&#xff0c;平台有项目管理、数据上传、场景搭建、发布分享、素材库等功能模块&#xff0c;支持多人在线协…...

CMake 学习笔记

一直想了解CMake&#xff0c;但是不知从何入门。最近看了CMake 官方的Tutorial&#xff0c;感觉的确很适合入门。 首先要安装CMake, 安装步骤: 直接去下载最新版Download | CMakemacos 点开CMake 后&#xff0c;遵循“How to Install For Command Line Use” 菜单项&#xff0…...

docker高级(DockerFile解析)

1、构建三步骤 编写Dockerfile文件 docker build命令构建镜像 docker run依镜像运行容器实例 2、DockerFile构建过程解析 Dockerfile内容基础知识 1&#xff1a;每条保留字指令都必须为大写字母且后面要跟随至少一个参数 2&#xff1a;指令按照从上到下&#xff0c;顺序执行…...