【C++搜索】BFS:走迷宫
题目描述
一个迷宫由R行C列格子组成,有的格子里有障碍物,不能走;有的格子是空地,可以走。
给定一个迷宫,求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走,不能斜着走。
输入
第一行是两个整数,R和C,代表迷宫的长和宽。( 1<= R,C <= 40)
接下来是R行,每行C个字符,代表整个迷宫。
空地格子用'.'表示,有障碍物的格子用'#'表示。
迷宫左上角和右下角都是'.'。
输出
输出从左上角走到右下角至少要经过多少步(即至少要经过多少个空地格子)。计算步数要包括起点和终点。
样例输入 Copy
5 5 ..### #.... #.#.# #.#.# #.#..
样例输出 Copy
9
#include <bits/stdc++.h>
using namespace std;
char a[50][50];
int d[50][50];
int r, c;
pair<int, int> q[2510];
void bfs()
{int hh = 0, tt = 0;q[0] = { 0,0 };d[0][0] = 0;memset(d, -1, sizeof d);int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };while (hh <= tt){auto t = q[hh++];for (int i = 0; i < 4; i++){int x = t.first + dx[i], y = t.second + dy[i];if (x >= 0 && x < r && y >= 0 && y <= c && a[x][y] == '.' && d[x][y] == -1){d[x][y] = d[t.first][t.second] + 1;q[++tt] = { x,y };}}}cout << d[r - 1][c - 1] + 2;return;
}int main()
{memset(a, '#', sizeof a);cin >> r >> c;for (int i = 0; i < r; i++)for (int j = 0; j < c; j++)cin >> a[i][j];bfs();return 0;
}
相关文章:
【C++搜索】BFS:走迷宫
题目描述 一个迷宫由R行C列格子组成,有的格子里有障碍物,不能走;有的格子是空地,可以走。 给定一个迷宫,求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走,不能斜着…...
SpringMVC 的参数绑定之list集合、Map
标签中name属性的值就是pojo类的属性名 参数绑定4 list [对象] <form action"teaupd.do" method"post"> <c:forEach items"${list}" var"tea" varStatus "status"> 教师编号:<input…...
Code Composer Studio (CCS) - Current and Local Revision
Code Composer Studio [CCS] - Current and Local Revision References 鼠标放在文件内的任意位置,鼠标右键 -> Compare With -> Local History -> Revision Time. References [1] Yongqiang Cheng, https://yongqiang.blog.csdn.net/...
Vue实现多个input输入,光标自动聚焦到下一个input
遇到一个需求,需要实现和移动端短信输入一样,输入内容后,光标会进入下一个输入框 需要用到2个事件 keydown事件发生在键盘的键被按下的时候 keyup 事件在按键被释放的时候触发 <template><div class"box"><el-fo…...
人工智能技术应用笔记(二):OpenAI SORA文生视频模型技术报告全文中英对照 (GPT4翻译+人工润色)
目录 Video generation models as world simulators(视频生成模型作为世界模拟器) Turning visual data into patches (将视觉数据转换为图像块) Video compression network (视频压缩网络) Spacetim…...
Linux-系统资源管理的命令
目录 查看CPU:more /proc/meminfo 查看内存数据:free -m / free -h 查看系统版本:more /etc/issue 查看操作系统的类型:uname -a 查看主机名称:hostname 查看磁盘空间:df -h 查看某个目录空间…...
Html的<figure><figcaption>标签
Html的<figure><figcaption>标签 示例一: <figure><figcaption>figcaption001, fig标题1 </figcaption><figcaption>figcaption002, fig标题2 </figcaption><div style"width:calc(100px*2); height:calc(100px*2); back…...
Selenium实现多页面切换
当使用 Selenium 进行自动化测试或爬取数据时,有时需要处理多个页面之间的切换。以下是一些可能需要多页面切换的情况: 1、打开新窗口/页面: 在当前页面上点击链接、按钮或执行某些操作时,可能会打开一个新的窗口或页面。此时&a…...
Electron实战之菜单与托盘
菜单、托盘是桌面端应用必备的功能之一,我们通常会在菜单上配置应用常用的:偏好设置、显示隐藏、打开文件等功能,在托盘内设置:退出、重启、帮助等辅助性功能,帮助用户方便快捷地控制应用的一些系统功能。系统托盘实际…...
【Java EE初阶十六】网络原理(一)
在网络原理中主要学习TCP/IP四层模型中的重点网络协议 1. 应用层 1.1 应用程序与协议 应用层是和程序员接触最密切的; 应用程序:在应用层这里,很多时候都是程序员自定义应用层协议(步骤:1、根据需求,明确…...
51_蓝桥杯_led流水灯
一 原理图分析 二 三八译码器工作原理 三八译码器:3个输入控制8路互斥的低电平有效输出。 C B A 输出 0 0 0 Y0 0 0 1 Y1 0 1 0 Y2 0 1 1 Y3 1 0 0 Y4 1 0 1 Y5 1 1 0 Y6 1 1 1 Y7 三 锁存器工作原理 锁存器:当使…...
⭐北邮复试刷题589. N 叉树的前序遍历__DFS (力扣每日一题)
589. N 叉树的前序遍历 给定一个 n 叉树的根节点 root ,返回 其节点值的 前序遍历 。 n 叉树 在输入中按层序遍历进行序列化表示,每组子节点由空值 null 分隔(请参见示例)。 示例 1: 输入:root [1,null,…...
php伪协议之phar
一.phar协议 用于将多个 PHP 文件、类、库、资源(如图像、样式表)等打包成一个单独的文件。这个归档文件可以像其他 PHP 文件一样被包含(include)或执行。PHAR 归档提供了一种方便的方式来分发和安装 PHP 应用程序和库,…...
蓝桥杯电子类单片机提升三——NE555
目录 单片机资源数据包_2023 一、NE555和定时器工作模式 1.NE555的介绍 2.定时器的计数模式 二、NE555频率读取代码的实现 1.定时器0初始化 2.通过读取TH0和TL0来读取频率 3.通过中断读取频率 三、完整代码演示 通过读取TH0和TL0来读取频率 main.c 通过中断读取频…...
发掘GPT-4商业创新的潜力
GPT-4在商业创新方面的应用潜力巨大,它能够基于庞大的训练数据集和强大的语言生成能力,协助企业或个人用户在多个商业场景中推动创新: 市场分析与战略规划:GPT-4可以对历史数据、行业趋势、竞争对手信息进行深度分析,并…...
LeetCode42.接雨水(单调栈)
题目 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例 : 输入:height [0,1,0,2,1,0,1,3,2,1,2,1] 输出:6 解释:上面是由数组 [0,1,0,2,1,0,1,3,2,…...
黄东旭:“向量数据库”还是“向量搜索插件 + SQL 数据库”?丨我对 2024 年数据库发展趋势的思考
本文由 PingCAP 黄东旭撰写,讨论了数据库技术在 2023 年的快速变革,并对 2024 年的数据库发展趋势进行了预测。文章重点关注了 GenAI 时代对数据库的影响,提出了在数据库选择上的两种路径:“向量数据库”和“向量搜索插件 SQL 数…...
Spark编程实验五:Spark Structured Streaming编程
目录 一、目的与要求 二、实验内容 三、实验步骤 1、Syslog介绍 2、通过Socket传送Syslog到Spark 3、Syslog日志拆分为DateFrame 4、对Syslog进行查询 四、结果分析与实验体会 一、目的与要求 1、通过实验掌握Structured Streaming的基本编程方法; 2、掌握…...
【已解决】引发的异常: 0xC0000005: 读取位置 0xFFFFFFFFFFFFFFFF 时发生访问冲突。
这种问题产生一般都会手足无措,包括笔者,但是不要慌,这种问题一般都是内存泄漏引起的。例如读者要访问一个已经被析构或者释放的变量,当然访问不了,导致存在问题。这时候读者应该从哪里产生内存泄漏这方面进行考虑&…...
Python Flask高级编程之RESTFul API前后端分离(学习笔记)
Flask-RESTful是一个强大的Python库,用于构建RESTful APIs。它建立在Flask框架之上,提供了一套简单易用的工具,可以帮助你快速地创建API接口。Flask-RESTful遵循REST原则,支持常见的HTTP请求方法,如GET、POST、PUT和DE…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
2.Vue编写一个app
1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...
安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)
船舶制造装配管理现状:装配工作依赖人工经验,装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书,但在实际执行中,工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...
【Go语言基础【12】】指针:声明、取地址、解引用
文章目录 零、概述:指针 vs. 引用(类比其他语言)一、指针基础概念二、指针声明与初始化三、指针操作符1. &:取地址(拿到内存地址)2. *:解引用(拿到值) 四、空指针&am…...
C++:多态机制详解
目录 一. 多态的概念 1.静态多态(编译时多态) 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1).协变 2).析构函数的重写 5.override 和 final关键字 1&#…...
第7篇:中间件全链路监控与 SQL 性能分析实践
7.1 章节导读 在构建数据库中间件的过程中,可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中,必须做到: 🔍 追踪每一条 SQL 的生命周期(从入口到数据库执行)&#…...
Python 实现 Web 静态服务器(HTTP 协议)
目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1)下载安装包2)配置环境变量3)安装镜像4)node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1)使用 http-server2)详解 …...
PHP 8.5 即将发布:管道操作符、强力调试
前不久,PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5!作为 PHP 语言的又一次重要迭代,PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是,借助强大的本地开发环境 ServBay&am…...
