走出迷宫(多组输入bfs)
链接:登录—专业IT笔试面试备考平台_牛客网
来源:牛客网
题目描述
小明现在在玩一个游戏,游戏来到了教学关卡,迷宫是一个N*M的矩阵。
小明的起点在地图中用“S”来表示,终点用“E”来表示,障碍物用“#”来表示,空地用“.”来表示。
障碍物不能通过。小明如果现在在点(x,y)处,那么下一步只能走到相邻的四个格子中的某一个:(x+1,y),(x-1,y),(x,y+1),(x,y-1);
小明想要知道,现在他能否从起点走到终点。
输入描述:
本题包含多组数据。 每组数据先输入两个数字N,M 接下来N行,每行M个字符,表示地图的状态。 数据范围: 2<=N,M<=500 保证有一个起点S,同时保证有一个终点E.
输出描述:
每组数据输出一行,如果小明能够从起点走到终点,那么输出Yes,否则输出No
示例1
输入
复制3 3 S.. ..E ... 3 3 S## ### ##E
3 3 S.. ..E ... 3 3 S## ### ##E
输出
复制Yes No
Yes No
分析:
注意多组输入,记得初始化
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct fx{ll x,y;
};
ll n,m;
queue<fx> q;
char g[502][502];
ll used[502][502];
ll dx[]={0,1,0,-1},dy[]={1,0,-1,0};
void init()
{queue<fx> q1;q=q1;memset(used,0,sizeof(used));
}
void bfs()
{while(q.size()){auto a=q.front();q.pop();for(ll i=0;i<4;i++){ll x=a.x+dx[i],y=a.y+dy[i];if(x<1||x>n||y<1||y>m)continue;if(used[x][y])continue;if(g[x][y]=='#')continue;used[x][y]=1;if(g[x][y]=='E'){cout<<"Yes"<<'\n';return ;}q.push({x,y});}}cout<<"No"<<'\n';
}
void solve()
{while(cin>>n>>m){init();for(ll i=1;i<=n;i++){for(ll j=1;j<=m;j++){cin>>g[i][j];if(g[i][j]=='S'){q.push({i,j});used[i][j]=1;}}}bfs();}
}
int main()
{ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);solve();return 0;
}
相关文章:
走出迷宫(多组输入bfs)
链接:登录—专业IT笔试面试备考平台_牛客网 来源:牛客网 题目描述 小明现在在玩一个游戏,游戏来到了教学关卡,迷宫是一个N*M的矩阵。 小明的起点在地图中用“S”来表示,终点用“E”来表示,障碍物用“#…...
Linux系统编程-终端、进程组、会话
一、终端的概念 在UNIX系统中,用户通过终端登录系统后得到一个Shell进程,这个终端成为Shell进程的控制终端(Controlling Terminal),进程中,控制终端是保存在PCB中的信息,而fork会复制PCB中的信息…...
Linux部分文件操作记录
问题描述 多级文件夹下,有多个同名文件,以及其他无关文件,为了减轻体量,遍历目录,只保留对应文件 首先open terminal here find . -type f \( ! -name algo_imu.bin -a ! -name post_gnss_only_error.log -a ! -name…...
Android系统-进程-Binder2-Java层
引言: 对于Android系统,一般是从java层到native层,再到kernel驱动层,形成一个完整的软件架构。Android系统中的Binder IPC通信机制的整体架构,从java层到底层驱动层是怎么样的一个架构和原理的呢? 概念与…...
体渲染原理及WebGL实现【Volume Rendering】
体渲染(Volume Rendering)是NeRF神经场辐射AI模型的基础,与传统渲染使用三角形来显示 3D 图形不同,体渲染使用其他方法,例如体积光线投射 (Volume Ray Casting)。本文介绍体渲染的原理并提供Three.js实现代码ÿ…...
VUE3组件
组件基础 {#components-basics} 组件允许我们将 UI 划分为独立的、可重用的部分,并且可以对每个部分进行单独的思考。在实际应用中,组件常常被组织成层层嵌套的树状结构: 这和我们嵌套 HTML 元素的方式类似,Vue 实现了自己的组件…...
【iOS】autoreleasepool
来说一下最近在了解的autoreleasepool吧,我们可能平时书写过许多脑残代码,其有很多的缺陷但是我们可能当时学的比较浅就也不太了解,就像下面这样的: for (int i 0; i < 1000000; i) {NSNumber *num [NSNumber numberWithInt…...
0基础学习VR全景平台篇 第80篇:Insta360 影石如何直播推流
一、下载Insta360 Pro APP 1、手机进入Insta360官网Insta360 | Action Cameras | 360 Cameras | VR Cameras,页面往下滑动到Insta360 Pro2相机处,点击相机图片进入详情页。详情页继续下滑到到手机APP处,根据自己的手机系统选择对应的客户端进…...
大语言模型之三 InstructGPT训练过程
大语言模型 GPT历史文章中简介的大语言模型的的发展史,并且简要介绍了大语言模型的训练过程,本篇文章详细阐述训练的细节和相关的算法。 2020年后全球互联网大厂、AI创业公司研发了不少AI超大模型(百亿甚至千亿参数),…...
ChatGPT在自动化报告和数据分析中的应用如何?
ChatGPT在自动化报告和数据分析领域的应用正日益受到关注,这种强大的语言模型不仅可以加速报告生成的过程,还可以辅助数据分析,从而帮助企业和个人更高效地处理信息和做出决策。以下将详细探讨ChatGPT在自动化报告和数据分析中的应用。 **自…...
面试热题(三数之和)
给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k ,同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三元组。 注意:答案中不可以包含重复的三元组。 输入&…...
在idea运行python文件
在idea运行python文件 如果在idea运行python文件而没有弹出run的选项,则点击File->Settings…->Plugins,在里面搜索python,如果没有显示则在Maketplace进行搜索, 接着Install,然后restart...
SQL - limit
介绍: limit 是限制的意思, 用于限制返回的查询结果的行数(可以通过limit指定查询多少行数据). MySQL支持limit语法, 用来完成分页. 用法: select 字段1, 字段2, ... from table_name limit offset, length;参数说明: offset: 起始行数, 从0开始计数, 如果省略, 则默认为…...
11. Redis基础知识
文章目录 一、概述二、数据类型STRINGLISTSETHASHZSET 三、数据结构字典跳跃表 四、使用场景计数器缓存查找表消息队列会话缓存分布式锁实现其它 五、Redis 与 Memcached数据类型数据持久化分布式内存管理机制 六、键的过期时间七、数据淘汰策略八、持久化RDB 持久化AOF 持久化…...
list模拟实现【引入反向迭代器】
文章目录 1.适配器1.1传统意义上的适配器1.2语言里的适配器1.3理解 2.list模拟实现【注意看反向迭代器】2.1 list_frame.h2.2riterator.h2.3list.h2.4 vector.h2.5test.cpp 3.反向迭代器的应用1.使用要求2.迭代器的分类 1.适配器 1.1传统意义上的适配器 1.2语言里的适配器 容…...
【华为OD机试】字符串变换最小字符串【2023 B卷|100分】
【华为OD机试】-真题 !!点这里!! 【华为OD机试】真题考点分类 !!点这里 !! 题目描述: 给定一个字符串s,最多只能进行一次变换,返回变换后能得到的最小字符串(按照字典序进行比较)。 变换规则:交换字符串中任意两个不同位置的字符。 输入描述: 一串小写字母组成的字…...
ARTS 挑战打卡的第8天 ---volatile 关键字在MCU中的作用,四个实例讲解(Tips)
前言 (1)volatile 关键字作为嵌入式面试的常考点,很多人都不是很了解,或者说一知半解。 (2)可能有些人会说了,volatile 关键字不就是防止编译器优化的吗?有啥好详细讲解的࿱…...
第二课-一键安装SD-Stable Diffusion 教程
前言 看完这篇文章并跟着操作,就可以在本地开始 SD 绘图了。 理论上来说,这篇课程结束,想要画什么图都可以画了。 启动器介绍 SD 是开源的,可以在 github 上找到。但直接下载源码安装,非常费劲,而且因为国内外差异,就是我这样的秃头程序员也难以应对。 所以,我们改…...
Vue3 动态列 <el-table-column> 实现 formatter 的两种方法
文章目录 动态列实现动态列实现formatter第一种第二种方法 动态列实现 参考此篇文章 Vue3 动态列实现 动态列实现formatter 第一种 以此为例:传递该行的wxUserInfo字段(对象)中的nickName 假设该行 {prop: "wxUserInfo", label: …...
室温超导是什么?有哪些应用场景?
目录 一、应用场景:二、案例分析: 室温超导是指在室温下(即约 20C 至 30C)实现超导现象的材料。超导是指某些材料在低温下电阻为零的物理现象,室温超导材料是超导材料的一种。室温超导现象的发现和研究是超导领域的一个…...
智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...
对WWDC 2025 Keynote 内容的预测
借助我们以往对苹果公司发展路径的深入研究经验,以及大语言模型的分析能力,我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际,我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测,聊作存档。等到明…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
用docker来安装部署freeswitch记录
今天刚才测试一个callcenter的项目,所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...
C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...
FFmpeg:Windows系统小白安装及其使用
一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】,注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录(即exe所在文件夹)加入系统变量…...
