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

DFS 算法:洛谷B3625迷宫寻路

在这里插入图片描述

我的个人主页 {\large \mathsf{{\color{Red} 我的个人主页} } } 我的个人主页

往 {\color{Red} {\Huge 往} } 期 {\color{Green} {\Huge 期} } 文 {\color{Blue} {\Huge 文} } 章 {\color{Orange} {\Huge 章}}

  • DFS 算法:记忆化搜索
  • DFS 算法:全排列问题

此系列更新频繁,求各位读者点赞
关注我可以了解更多内容哦
偷偷告诉你,我正在冲 1100 粉 {\color{Gray} {\small 偷偷告诉你,我正在冲1100粉} } 偷偷告诉你,我正在冲1100
你们有什么想了解的可以发在评论区,我会仔细的看 {\color{Gray} {\small 你们有什么想了解的可以发在评论区,我会仔细的看} } 你们有什么想了解的可以发在评论区,我会仔细的看
1100 粉时我会抓几个做文章 {\color{Gray} {\small1100粉时我会抓几个做文章} } 1100粉时我会抓几个做文章


目录

  • 今天我们学什么
  • 例题
    • 题目描述
    • 输入格式
    • 输出格式
    • 样例 #1
      • 样例输入 #1
      • 样例输出 #1
    • 提示
        • 样例解释
        • 数据规模与约定
    • 题解
      • 错误示范
      • 正确代码
  • 总结

今天我们学什么

今天我们不学什么,就是做一道二维DFS的题目

例题

我们选用了洛谷题目:B3625 迷宫寻路

题目描述

机器猫被困在一个矩形迷宫里。

迷宫可以视为一个 n × m n\times m n×m 矩阵,每个位置要么是空地,要么是墙。机器猫只能从一个空地走到其上、下、左、右的空地。

机器猫初始时位于 ( 1 , 1 ) (1, 1) (1,1) 的位置,问能否走到 ( n , m ) (n, m) (n,m) 位置。

输入格式

第一行,两个正整数 n , m n,m n,m

接下来 n n n 行,输入这个迷宫。每行输入一个长为 m m m 的字符串,# 表示墙,. 表示空地。

输出格式

仅一行,一个字符串。如果机器猫能走到 ( n , m ) (n, m) (n,m),则输出 Yes;否则输出 No

样例 #1

样例输入 #1

3 5
.##.#
.#...
...#.

样例输出 #1

Yes

提示

样例解释

路线如下: ( 1 , 1 ) → ( 2 , 1 ) → ( 3 , 1 ) → ( 3 , 2 ) → ( 3 , 3 ) → ( 2 , 3 ) → ( 2 , 4 ) → ( 2 , 5 ) → ( 3 , 5 ) (1,1)\to (2,1) \to (3,1) \to (3,2)\to (3,3) \to (2, 3) \to (2, 4) \to (2, 5) \to (3, 5) (1,1)(2,1)(3,1)(3,2)(3,3)(2,3)(2,4)(2,5)(3,5)

数据规模与约定

对于 100 % 100\% 100% 的数据,保证 1 ≤ n , m ≤ 100 1 \leq n, m \leq 100 1n,m100,且 ( 1 , 1 ) (1,1) (1,1) ( n , m ) (n, m) (n,m) 均为空地。


在这里插入图片描述


题解

错误示范

我们第一时间可以想到,这是一道简单的二维DFS题目,随便一些就能AC,这大概是你想到的代码:

#include <bits/stdc++.h>
using namespace std;
char a[105][105];
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
int n,m;
bool vis[105][105];
void dfs(int x,int y)
{if(x<1 || x>n || y<1 || y>m || a[x][y]=='#'){return; }if(x==n && y==m){cout<<"Yes";exit(0);}for(int i=0; i<=3; i++){int tx=x+dx[i];int ty=y+dy[i];if(!vis[tx][ty]){vis[tx][ty]=1;dfs(tx,ty);vis[tx][ty]=0;}}
}int main()
{cin>>n>>m;for(int i=1; i<=n ;i++){string s;cin>>s;for(int j=0; j<m; j++){a[i][j+1]=s[j];}}dfs(1,1);cout<<"No";return 0;
}

但是这样你只能得到10分
在这里插入图片描述

此时,我们可以想一想,你为什么需要回溯呢?
删除vis[tx][ty]=0;即可AC

正确代码

为了方便阅读,我直接给出了正确代码(我做人太好了

#include <bits/stdc++.h>
using namespace std;
char a[105][105];
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
int n,m;
bool vis[105][105];
void dfs(int x,int y)
{if(x<1 || x>n || y<1 || y>m || a[x][y]=='#'){return; }if(x==n && y==m){cout<<"Yes";exit(0);}for(int i=0; i<=3; i++){int tx=x+dx[i];int ty=y+dy[i];if(!vis[tx][ty]){vis[tx][ty]=1;dfs(tx,ty);}}
}int main()
{cin>>n>>m;for(int i=1; i<=n ;i++){string s;cin>>s;for(int j=0; j<m; j++){a[i][j+1]=s[j];}}dfs(1,1);cout<<"No";return 0;
}

怎么样,这是不是很简单呢?

总结

做题要思考!!!

相关文章:

DFS 算法:洛谷B3625迷宫寻路

我的个人主页 {\large \mathsf{{\color{Red} 我的个人主页} } } 我的个人主页 往 {\color{Red} {\Huge 往} } 往 期 {\color{Green} {\Huge 期} } 期 文 {\color{Blue} {\Huge 文} } 文 章 {\color{Orange} {\Huge 章}} 章 DFS 算法&#xff1a;记忆化搜索DFS 算法&#xf…...

结构开发笔记(七):solidworks软件(六):装配摄像头、摄像头座以及螺丝,完成摄像头结构示意图

若该文为原创文章&#xff0c;转载请注明原文出处 本文章博客地址&#xff1a;https://hpzwl.blog.csdn.net/article/details/141931518 长沙红胖子Qt&#xff08;长沙创微智科&#xff09;博文大全&#xff1a;开发技术集合&#xff08;包含Qt实用技术、树莓派、三维、OpenCV…...

Android 15 新特性快速解读指南

核心要点 16K 页面大小支持目前作为开发人员选项提供&#xff0c;并非强制要求。 引入多项提升开发体验、多语言支持、多媒体功能、交互体验和隐私安全的更新。 重点关注前台服务限制、Window Insets 行为变化、AndroidManifest 文件限制等适配要求。 开发体验 ApplicationS…...

【机器人工具箱Robotics Toolbox开发笔记(十九)】机器人工具箱Link类函数参数说明

​机器人工具箱中的Link对象保存于机器人连杆相关的所有信息,如运动学参数、刚体惯性参数、电机和传动参数等。 与Link对象有关参数如表1所示。 表1 Link对象参数 参 数 意 义 参 数 意 义 A 连杆变换矩阵 islimit 测试关节是否超过软限制 RP RP关节类型 isrevo…...

排查SQL Server中的内存不足及其他疑难问题

文章目录 引言I DMV 资源信号灯资源信号灯 DMV sys.dm_exec_query_resource_semaphores( 确定查询执行内存的等待)查询性能计数器什么是内存授予?II DBCC MEMORYSTATUS 查询内存对象III DBCC 命令释放多个 SQL Server 内存缓存 - 临时度量值IV 等待资源池 %ls (%ld)中的内存…...

输送线相机拍照信号触发(博途PLC高速计数器中断立即输出应用)

博途PLC相关中断应用请参考下面文章链接: T法测速功能块 T法测速功能块(博途PLC上升沿中断应用)-CSDN博客文章浏览阅读165次。本文介绍了博途PLC中T法测速的原理和应用,包括如何开启上升沿中断、配置中断以及T法测速功能块的使用。重点讲述了在中断事件发生后执行的功能块处…...

【数学分析笔记】第3章第1节 函数极限(6)

3. 函数极限与连续函数 3.1 函数极限 【例3.1.12】 f ( x ) a n x n a n − 1 x n − 1 ⋯ a k x k b m x m b m − 1 x m − 1 ⋯ b j x j , b m , b j ≠ 0 , a n , a k ≠ 0 f(x) \frac{a_{n} x^{n}a_{n-1} x^{n-1}\cdotsa_{k} x^{k}}{b_{m} x^{m}b_{m-1} x^{m-1}\…...

程序员如何写笔记?

word。没错&#xff0c;我也看了网上一大堆软件&#xff0c;还有git管理等等。个人认为如果笔记只是记录个人的经验积累&#xff0c;一个word就够了&#xff0c;那些notepad&#xff0c;laTex个人觉得不够简练。word。 1.word可以插入任何文件附件(目前最大的word 200MB也没出现…...

Linux网络——Socket编程函数

一.网络命令 1.ping ping命令用来检测网络是否连通&#xff0c;具体用法为&#xff1a; ping 任意网址 结果如下&#xff1a; 当出现上述字段时&#xff0c;证明网络是连通的&#xff0c;这里值得注意的是&#xff0c;ping命令执行之后会不断进行网络检测&#xff0c;不会停…...

HarmonyOS 是如何实现一次开发多端部署 -- HarmonyOS自学1

一次开发多端部署遇到的几个关键问题 为了实现“一多”的目标&#xff0c;需要解决如下三个基础问题&#xff1a; 问题1&#xff1a;页面如何适配 不同设备间的屏幕尺寸、色彩风格等存在差异&#xff0c;页面如何适配。 问题2&#xff1a;功能如何兼容 不同设备的系统能力…...

嵌入式硬件-ARM处理器架构,CPU,SOC片上系统处理器

多进程空间内部分布图&#xff1a;注意&#xff1a;创建线程实际使用堆区空间&#xff0c;栈区独立 ARM处理器架构&#xff1a; 基于ARM920T架构的CPU:以下为哈佛结构 ALU:算数运算器 R0~R12&#xff1a;寄存器 PC:程序计数器&#xff0c;默认为0&#xff0c;做自加运算&#x…...

《JavaEE进阶》----12.<SpringIOCDI【扫描路径+DI详解+经典面试题+总结】>

本篇博客主要讲解 扫描路径 DI详解&#xff1a;三种注入方式及优缺点 经典面试题 总结 五、环境扫描路径 虽然我们没有告诉Spring扫描路径是什么&#xff0c;但是有一些注解已经告诉Spring扫描路径是什么了 如启动类注解SpringBootApplication。 里面有一个注解是componentS…...

Selenium 自动化测试:常用函数与实例代码

引言 Selenium 是一个强大的自动化测试工具&#xff0c;广泛用于网页应用的自动化测试。它支持多种编程语言&#xff0c;包括 Python。本文将介绍 Selenium 的常用函数&#xff0c;并提供参数解释和代码示例。 Selenium 简介 Selenium 是一个用于自动化 Web 应用测试的工具&…...

python网络爬虫(五)——爬取天气预报

1.注册高德天气key 点击高德天气&#xff0c;然后按照开发者文档完成key注册&#xff1b;作为爬虫练习项目之一。从高德地图json数据接口获取天气&#xff0c;可以获取某省的所有城市天气&#xff0c;高德地图的这个接口还能获取县城的天气。其天气查询API服务地址为https://re…...

四.海量数据实时分析-Doris数据导入导出

数据导入 1.概述 Apache Doris 提供多种数据导入方案&#xff0c;可以针对不同的数据源进行选择不同的数据导入方式。 数据源导入方式对象存储&#xff08;s3&#xff09;,HDFS使用 Broker 导入数据本地文件Stream Load, MySQL LoadKafka订阅 Kafka 数据Mysql、PostgreSQL&a…...

一. 从Hive开始

1. 怎么理解Hive Hive不能理解成一个传统意义上的数据库&#xff0c;应该理解成一个解决方案。 是Hadoop在hdfs和mapreduce之后才出现的一个结构化数据处理的解决方案。 Hdfs解决了大数据的存储问题&#xff0c;mapreduce解决了数据的计算问题。 一切似乎很美好。 但是使用成本…...

Linux下的PWM驱动

PWM PWM简介⭕ **PWM&#xff08;Pulse Width Modulation&#xff0c;脉冲宽度调制&#xff09;**是一种利用微处理器的数字输出对模拟电路进行控制的技术。通过改变脉冲的占空比&#xff0c;可以控制模拟电路的输出电压或电流。PWM技术广泛应用于电机控制、灯光调节、音频信号…...

日语输入法平假名和片假名切换

在学日语输入法的时候&#xff0c;我们在使用罗马音输入的时候&#xff0c;在进行平假名和片假名切换&#xff1a; 1、使用电脑在打字&#xff0c;日语输入法切换的时候使用 Shift Alt 如果日语输入法显示为 A 需要切换为 あ的话可以按Caps Lock键 。&#xff08;相当于中文…...

Oracle向量搜索及其应用场景

Oracle 向量搜索&#xff08;AI Vector Search&#xff09;是一个集成到 Oracle 数据库中的功能&#xff0c;旨在优化人工智能&#xff08;AI&#xff09;工作负载。它允许用户存储和查询非结构化数据的语义内容&#xff0c;如文档、图像等&#xff0c;形式为向量。 向量数据类…...

【排序算法】六、快速排序补充:三指针+随机数法

「前言」文章内容是对快速排序算法的补充&#xff0c;之前的算法流程细节多难处理&#xff0c;这里补充三指针随机数法&#xff08;递归&#xff09;&#xff0c;这个容易理解&#xff0c;在时间复杂度上也更优秀。 快排&#xff1a;三指针随机数法 原理跟之前的一致&#xff…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...

十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建

【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...

高考志愿填报管理系统---开发介绍

高考志愿填报管理系统是一款专为教育机构、学校和教师设计的学生信息管理和志愿填报辅助平台。系统基于Django框架开发&#xff0c;采用现代化的Web技术&#xff0c;为教育工作者提供高效、安全、便捷的学生管理解决方案。 ## &#x1f4cb; 系统概述 ### &#x1f3af; 系统定…...

OCR MLLM Evaluation

为什么需要评测体系&#xff1f;——背景与矛盾 ​​ 能干的事&#xff1a;​​ 看清楚发票、身份证上的字&#xff08;准确率>90%&#xff09;&#xff0c;速度飞快&#xff08;眨眼间完成&#xff09;。​​干不了的事&#xff1a;​​ 碰到复杂表格&#xff08;合并单元…...

基于开源AI智能名片链动2 + 1模式S2B2C商城小程序的沉浸式体验营销研究

摘要&#xff1a;在消费市场竞争日益激烈的当下&#xff0c;传统体验营销方式存在诸多局限。本文聚焦开源AI智能名片链动2 1模式S2B2C商城小程序&#xff0c;探讨其在沉浸式体验营销中的应用。通过对比传统品鉴、工厂参观等初级体验方式&#xff0c;分析沉浸式体验的优势与价值…...