走出迷宫的最少步数and第一条出路
题面
题目描述
一个迷宫由 R 行 C 列格子组成,有的格子里有障碍物,不能走;有的格子是空地,可以走。
给定一个迷宫,求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走,不能斜着走。
输入
第一行是两个整数,R 和 C ,代表迷宫的行数和列数。( 1≤R,C≤40 )
接下来是 R 行,每行 C 个字符,代表整个迷宫。空地格子用
.表示,有障碍物的格子用#表示。迷宫左上角和右下角都是
.。输出
输出从左上角走到右下角至少要经过多少步(即至少要经过多少个空地格子)。
计算步数要包括起点和终点。
样例
输入
5 5 ..### #.... #.#.# #.#.# #.#..输出
9链接:Link.
最少步数问题,可以准备一个步数数组,记录从出发点到每个点至少多少步,然后不断替换最少步数,知道找出最优解。
#include <bits/stdc++.h>
using namespace std;
char a[50][50];
int fx[5] = {0 , 0 , 1 , 0 , -1} , fy[5] = {0 , 1 , 0 , -1 , 0};
int d[50][50] , n , m;
void dfs( int x , int y , int dep ){d[x][y] = dep;int tx , ty;for ( int i = 1 ; i <= 4 ; i++ ){tx = x + fx[i];ty = y + fy[i];if ( a[tx][ty] == '.' && dep + 1 < d[tx][ty] )dfs(tx , ty , dep+1);}
}
int main(){scanf("%d%d" , &n , &m);for ( int i = 1 ; i <= n ; i++ )for ( int j = 1 ; j <= m ; j++ ){cin >>a[i][j];d[i][j] = INT_MAX; }dfs(1 , 1 , 1);printf("%d" , d[n][m]);return 0;
}
这题还有个变种,就是给定起点和终点,求最少步数(要注意第一次到终点不一定是最优解,所以要return一下)
#include <bits/stdc++.h>
using namespace std;
char a[110][110];
int n , m , s1 ,s2 , e1 , e2 , d[110][110];
int fx[5] = {0 , 0 , 1 , 0 , -1},fy[5] = {0 , 1 , 0 , -1 , 0};
void dfs(int x , int y , int k){d[x][y] = k;if(x == e1 && y == e2){return;}int tx , ty;for( int i = 1 ; i <= 4 ; i++ ){tx = x + fx[i];ty = y + fy[i];if( (a[tx][ty] == '.' || a[tx][ty] == 'T') && k + 1 < d[tx][ty] )dfs(tx , ty , k+1);}
}
int main(){scanf("%d%d" , &n , &m);for ( int i = 1 ; i <= n ; i++ )for ( int j = 1 ; j <= m ; j++ ){cin >> a[i][j];if( a[i][j] == 'S' ){s1 = i;s2 = j;}else if(a[i][j] == 'T'){e1 = i;e2 = j;}d[i][j] = INT_MAX;}dfs(s1 , s2 , 0);printf("%d" , d[e1][e2]);return 0;
}
迷宫的第一条出路
题目描述
已知一 N×N 的迷宫,允许往上、下、左、右四个方向行走,现请你按照左、上、右、下顺序进行搜索,找出第一条从左上角到右下角的路径。
输入
输入数据有若干行,第一行有一个自然数 N(N≤20),表示迷宫的大小;
其后有 N 行数据,每行有 N 个 0 或 1(数字之间没有空格,0 表示可以通过,1 表示不能通过),用以描述迷宫地图。入口在左上角 (1,1)处,出口在右下角(N,N) 处。
所有迷宫保证存在从入口到出口的可行路径。
输出
输出数据仅一行,为按照要求的搜索顺序找到的从入口到出口的第一条路径(搜索顺序:左、上、右、下)
样例
输入
4 0001 0100 0010 0110输出
复制(1,1)->(1,2)->(1,3)->(2,3)->(2,4)->(3,4)->(4,4)链接
将路径的下标K作为递归参数,这样递归后退时K也会后退,从而覆盖原来的元素
代码
#include <bits/stdc++.h>
using namespace std;
int n , r[410][3];
int fx[5] = {0 , 0 , -1 , 0 , 1},fy[5] = {0 , -1 , 0 , 1 , 0};
char a[35][35];
void print(int k){for ( int i = 1 ; i <= k ; i++ ){printf("(%d,%d)" , r[i][1] , r[i][2]);if( i != k )printf("->");}
}
void dfs( int x , int y , int k){a[x][y] = '1';r[k][1] = x;r[k][2] = y;if ( x == n && y == n ){print(k);exit(0);}int tx , ty;for ( int i = 1 ; i <= 4 ; i++ ){tx = x + fx[i];ty = y + fy[i];if(a[tx][ty] == '0')dfs(tx , ty , k+1);}
}
int main(){scanf("%d" , &n);for ( int i = 1 ; i <= n ; i++ )for ( int j = 1 ; j <= n ; j++ )cin >> a[i][j];dfs(1,1,1);return 0;
}
相关文章:
走出迷宫的最少步数and第一条出路
题面 题目描述 一个迷宫由 R 行 C 列格子组成,有的格子里有障碍物,不能走;有的格子是空地,可以走。 给定一个迷宫,求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走,…...
MediaCodec创建对应解码器
媒体编解码API使用示例 //获取相关格式文件的内容信息,如轨道数量、获取MIME信息、视频的高度与宽度、语言格式、播放总时长等 MediaExtractor mediaExtractor new MediaExtractor(); try {mediaExtractor.setDataSource(path); // 设置数据源 } catch (IOExcept…...
使用eXosip+ffmpeg、ffplay命令行实现sip客户端
文章目录 前言一、关键实现1、主要流程2、解决端口冲突(1)、出现原因(2)、解决方法 3、解析sdp(1)、定义实体(2)、解析视频(3)、解析音频 4、命令行推拉流&am…...
dotNet 之网络TCP
**硬件支持型号 点击 查看 硬件支持 详情** DTU701 产品详情 DTU702 产品详情 DTU801 产品详情 DTU802 产品详情 DTU902 产品详情 G5501 产品详情 ARM dotnet 编程 dotNet使用TCP,可以使用Socket和TcpClient 、TcpListener类 2种,对于高级用户&…...
python基础面试题汇总(持续更新),冲击offer
目录 1.概念理解题python内置数据结构,哪些是不可变的python新式类和经典类的区别is和有什么区别Python中变量查找顺序python函数的参数是值传递还是引用传递python垃圾回收机制什么是闭包什么是装饰器,开发中用到举例如何实现只读属性Python中类方法、实…...
Java课题笔记~ AOP编程术语(掌握)
(1) 切面(Aspect) 切面泛指交叉业务逻辑。上例中的事务处理、日志处理就可以理解为切面。常用的切面是通知(Advice)。实际就是对主业务逻辑的一种增强。 (2) 连接点(Jo…...
暑假刷题第23天--8/6
3748. 递增子串 - AcWing题库 #include<iostream> #include<string> const int N200005; int a[N]; using namespace std; int main(){int t;cin>>t;for(int q1;q<t;q){int n;cin>>n;string s;cin>>s;int cnt1;a[1]1;for(int i2;i<n;i){i…...
ArcGIS API for JavaScript 4.x 教程(一) 显示一张地图
了解如何创建和显示带有基本地图图层的地图。 地图包含地理数据层。地图包含一个基本地图层,以及一个或多个数据层(可选)。可以使用地图视图显示地图的特定区域,并设置位置和缩放级别。 本教程将向您展示如何使用地形底图层创建和…...
Python-OpenCV中的图像处理
Python-OpenCV中的图像处理 颜色空间转换物体跟踪获取HSV的值几何变换图像缩放图像平移图像旋转仿射变换透视变换 图像阈值单阈值自适应阈值Otsus二值化 颜色空间转换 在 OpenCV 中有超过 150 中进行颜色空间转换的方法。但是你以后就会 发现我们经常用到的也就两种࿱…...
分清性能测试,负载测试,压力测试这三个的区别
做测试一年多来,虽然平时的工作都能很好的完成,但最近突然发现自己在关于测试的整体知识体系上面的了解很是欠缺,所以,在工作之余也做了一些测试方面的知识的补充。不足之处,还请大家多多交流,互相学习。 …...
前端架构师岗位的工作职责(合集)
前端架构师岗位的工作职责1 职责: 1.制定前端的标准和规范,并推广和应用,提高团队的开发效率; 2.前端架构的框架或核心模块的设计与实现; 3.在前端架构、设计与开发上对团队进行足够的指导; 4.在日常的系统设计与优化上与服务端团队紧密合…...
使用 Amazon ECS Anywhere 在边缘部署 Amazon IoT Greengrass
1.概述 亚马逊云科技提供了完备的IoT服务能力,涵盖设备服务、连接和控制服务以及云端分析服务,是快速构建安全可靠、可扩展的 IoT 平台的常见选择。Amazon IoT Greengrass 边缘运行时和云服务,可帮助您在设备上构建、部署和管理 IoT 应用。A…...
pytorch Stream 多流处理
CUD Stream https://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html#c-language-extensions 中指出在kenel的调用函数中最后一个可选参数表示该核函数处在哪个流之中。 - 参数Dg用于定义整个grid的维度和尺寸,即一个grid有多少个block。为dim3类型。…...
微信小程序选项卡切换(滑动切换,点击切换)
效果如下:可点击切换,滑动切换 代码如下 这个可以在项目用 index.wxml <view classtopTabSwiper><view classtab {{currentData 0 ? "tabBorer" : ""}} data-current "0" bindtapcheckCurrent>选项一&…...
安路FPGA的赋值报错——移位处理,加括号
authordaisy.skye的博客_CSDN博客-嵌入式,Qt,Linux领域博主 在使用移位符号用来当作除以号使用时,发现如下问题 其中 cnt_8K 为偶数和奇数时输出的数据不一样 reg [10:0] cnt_8K; reg [10:0] ram1_addra; always(posedge clk_16M) begin if(ram_out_flag )begin if(…...
GO学习之 接口(Interface)
GO系列 1、GO学习之Hello World 2、GO学习之入门语法 3、GO学习之切片操作 4、GO学习之 Map 操作 5、GO学习之 结构体 操作 6、GO学习之 通道(Channel) 7、GO学习之 多线程(goroutine) 8、GO学习之 函数(Function) 9、GO学习之 接口(Interface) 文章目录 GO系列前言一、什么是…...
ansible常见模块的运用
ansible常见模块的运用 一:Ansible简介二:ansible 环境安装部署管理端安装 ansibleansible 目录结构配置主机清单配置密钥对验证 三:ansible 命令行模块1.command 模块在远程主机执行命令,不支持管道,重定向…...
合宙Air724UG LuatOS-Air script lib API--patch
patch Table of Contents patch patch.safeJsonDecode(s) (local函数 无法被外部调用) patch 模块功能:Lua补丁 patch.safeJsonDecode(s) (local函数 无法被外部调用) 封装自定义的json.decode接口 参数 名称 传入值类型 释义 s string json格式的字符串 返回值 t…...
pytorch求导
pytorch求导的初步认识 requires_grad tensor(data, dtypeNone, deviceNone, requires_gradFalse)requires_grad是torch.tensor类的一个属性。如果设置为True,它会告诉PyTorch跟踪对该张量的操作,允许在反向传播期间计算梯度。 x.requires_grad 判…...
Java基础异常详解
Java基础异常详解 文章目录 Java基础异常详解编译时异常(Checked Exception):运行时异常(Unchecked Exception): Java中的异常是用于处理程序运行时出现的错误或异常情况的一种机制。 异常本身也是一个类。 异常分为…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
边缘计算医疗风险自查APP开发方案
核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...
第25节 Node.js 断言测试
Node.js的assert模块主要用于编写程序的单元测试时使用,通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试,通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...
什么是VR全景技术
VR全景技术,全称为虚拟现实全景技术,是通过计算机图像模拟生成三维空间中的虚拟世界,使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验,结合图文、3D、音视频等多媒体元素…...
React从基础入门到高级实战:React 实战项目 - 项目五:微前端与模块化架构
React 实战项目:微前端与模块化架构 欢迎来到 React 开发教程专栏 的第 30 篇!在前 29 篇文章中,我们从 React 的基础概念逐步深入到高级技巧,涵盖了组件设计、状态管理、路由配置、性能优化和企业级应用等核心内容。这一次&…...
算法—栈系列
一:删除字符串中的所有相邻重复项 class Solution { public:string removeDuplicates(string s) {stack<char> st;for(int i 0; i < s.size(); i){char target s[i];if(!st.empty() && target st.top())st.pop();elsest.push(s[i]);}string ret…...
HTML中各种标签的作用
一、HTML文件主要标签结构及说明 1. <!DOCTYPE html> 作用:声明文档类型,告知浏览器这是 HTML5 文档。 必须:是。 2. <html lang“zh”>. </html> 作用:包裹整个网页内容,lang"z…...
理想汽车5月交付40856辆,同比增长16.7%
6月1日,理想汽车官方宣布,5月交付新车40856辆,同比增长16.7%。截至2025年5月31日,理想汽车历史累计交付量为1301531辆。 官方表示,理想L系列智能焕新版在5月正式发布,全系产品力有显著的提升,每…...
