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

荷香堪筑梦,鸳鸯和月寻。(变相BFS搜索)

本题链接:登录—专业IT笔试面试备考平台_牛客网

题目:

样例:

输入
3 4 2
....
***.
..a.
输出
yes

思路:

        根据题意,这里 1 s 可以移动多次,我们将每次可以移动避开雪的的位置存储起来,判断当移动到了顶部,说明完全可以避开雪。

代码详解如下:

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#define endl '\n'
#define x first
#define y second
#define int long long
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;
inline void solve();signed main()
{
//	freopen("a.txt", "r", stdin);IOS;int _t = 1;// cin >> _t;while (_t--){solve();}return 0;
}
int n,m,k;
char g[1010][1010];		// 下雪图
bool st[1010][1010];	// 标记是否走过
using PII = pair<int,int>;
inline void BFS(int x,int y)
{queue<PII>q;q.emplace(x,y);st[x][y] = true;while(q.size()){PII now = q.front();q.pop();// 如果到达了最顶部,说明完全避开了所以雪if(now.x == 1){cout << "yes" << endl;return ;}st[now.x][now.y] = true;// 当前位置 的 上右边可移动最长距离int rlen = min(now.y + k,m);for(int i = now.y;i <= rlen;++i){// 如果这个位置没走过,我们存储起来可以走到这个的位置if(g[now.x - 1][i] == '.' and !st[now.x - 1][i]){// 标记这里走过了st[now.x - 1][i] = true;q.emplace(PII(now.x - 1,i));}}// 当前位置 的 上右边可移动最长距离int llen = min(now.y - k,1LL);for(int i = now.y - 1;i >= llen;--i){// 如果这个位置没走过,我们存储起来可以走到这个的位置if(g[now.x - 1][i] == '.' and !st[now.x - 1][i]){// 标记这里走过了st[now.x - 1][i] = true;q.emplace(PII(now.x - 1,i));}}}cout << "no" << endl;	// 如果一直走不到 顶部,输出no
}
inline void solve()
{int x,y;cin >> n >> m >> k;for(int i = 1;i <= n;++i){for(int j = 1;j <= m;++j){cin >> g[i][j];if(g[i][j] == 'a'){x = i;y = j;}}}BFS(x,y);
}

最后提交:

相关文章:

荷香堪筑梦,鸳鸯和月寻。(变相BFS搜索)

本题链接&#xff1a;登录—专业IT笔试面试备考平台_牛客网 题目&#xff1a; 样例&#xff1a; 输入 3 4 2 .... ***. ..a. 输出 yes 思路&#xff1a; 根据题意&#xff0c;这里 1 s 可以移动多次&#xff0c;我们将每次可以移动避开雪的的位置存储起来&#xff0c;判断当…...

智慧公厕建设,打造智慧城市基础设施新亮点

公共厕所是城市基础设施的重要组成部分&#xff0c;而智慧公厕的建设则是现代城市管理的创新之举。为了实现公厕的精细化管理和提供更便捷的服务&#xff0c;推进智慧公厕建设必须要实现技术融合、业务融合、数据融合的目标&#xff0c;跨越层级、地域、系统、部门和业务的限制…...

Kubernetes 教程:在 Containerd 容器中使用 GPU

原文链接:Kubernetes 教程:在 Containerd 容器中使用 GPU 云原生实验室本文介绍了如何在使用 Containerd 作为运行时的 Kubernetes 集群中使用 GPU 资源。https://fuckcloudnative.io/posts/add-nvidia-gpu-support-to-k8s-with-containerd/ 前两天闹得沸沸扬扬的事件不知道…...

LNMP部署wordpress

1.环境准备 总体架构介绍 序号类型名称外网地址内网地址软件02负载均衡服务器lb0110.0.0.5192.168.88.5nginx keepalived03负载均衡服务器lb0210.0.0.6192.168.88.6nginx keepalived04web服务器web0110.0.0.7192.168.88.7nginx05web服务器web0210.0.0.8192.168.88.8nginx06we…...

本地部署大模型ollama+docker+open WebUI/Lobe Chat

文章目录 大模型工具Ollama下载安装运行Spring Ai 代码测试加依赖配置写代码 ollama的web&Desktop搭建部署Open WebUI有两种方式Docker DesktopDocker部署Open WebUIDocker部署Lobe Chat可以配置OpenAI的key也可以配置ollama 大模型的选择 本篇基于windows环境下配置 大模型…...

qt学习篇---界面按键关联(信号和槽)

目录 1.qt基础 2.做一个界面 创建project UI界面设计 信号和槽 1.控件改名字 2.什么是信号和槽 3.怎么关联信号和槽 自动关联 手动关联 1.qt基础 qt可移植性强&#xff0c;不久会用到MCU。很有意义学习 2.做一个界面 创建project 不要中文路径 选择QWidget .pro文件…...

python Django 的内置权限系统或自定义模型来存储更复杂的角色和权限关系

在 Django 中,管理用户权限和角色通常涉及到使用 Django 的内置权限系统或自定义模型来存储更复杂的角色和权限关系。下面是一个基本的指南,说明如何在 Django 中为后台管理系统分配权限并将其保存在数据库中,同时结合 Vue.js 和 Element UI 作为前端框架。 后端(Django)…...

不上班,我靠这5份赚钱副业养活了自己

在这个快节奏的社会里&#xff0c;很多人都在为生活奔波忙碌。今天&#xff0c;就让我来跟大家分享一下我的“躺平”秘籍吧&#xff01; 这一个月来&#xff0c;我没有上班&#xff0c;但好在有副业养活自己。有时候&#xff0c;我真的觉得有一份自己喜欢的自媒体副业挺好的。…...

强一致性的皇冠:分布式事务模型的至高法则揭秘

关注微信公众号 “程序员小胖” 每日技术干货&#xff0c;第一时间送达&#xff01; 引言 分布式事务模型是分布式系统设计的核心&#xff0c;关键在于保证数据一致性和事务完整性&#xff0c;尤其强调强一致性。诸如2PC、3PC、Saga、TCC等模型与协议&#xff0c;应运而生以解…...

mac/windows下安装docker,minikube

1、安装docker Get Started | Docker 下载安装docker 就行 启动后&#xff0c;就可以正常操作docker了 使用docker -v 验证是否成功就行 2、安装minikube&#xff0c;是基于docker-desktop的 2.1、点击设置 2.2、选中安装&#xff0c;这个可能需要一点时间 这样安装后&…...

【爬虫】fake_useragent的使用、BeautifulSoup(find()和find_all())

1 fake_useragent 2 BeautifulSoup 3 Beautiful Soup库的find()和find_all() 1 fake_useragent fake_useragent是一个Python库&#xff0c;用于生成随机的用户代理字符串。 用户代理是在HTTP请求中发送给服务器的一种标识&#xff0c;它告诉服务器发送请求的客户端的类型、版本…...

ComfyUI中图像亮度/对比度/饱和度处理

用上面这个节点可以同时设置图片的亮度、对比度和饱和度。 【保姆级教程】一口气分享在ComfyUI中常用的30多种基本图像处理方式 更多好玩且实用AIGC工作流和节点 星球号&#xff1a;32767063 本期资料链接 往期学习资料 整理AI学习资料库...

基于FPGA的DDS波形发生器VHDL代码Quartus仿真

名称&#xff1a;基于FPGA的DDS波形发生器VHDL代码Quartus仿真&#xff08;文末获取&#xff09; 软件&#xff1a;Quartus 语言&#xff1a;VHDL 代码功能&#xff1a; DDS波形发生器VHDL 1、可以输出正弦波、方波、三角波 2、可以控制输出波形的频率 DDS波形发生器原理…...

C++语法|可调用对象与function类型

文章目录 引入function的使用function类型的典型应用function类型的原理实现代码优化可变参的函数对象 引入 还记得C语言中的函数指针数组吗&#xff1f; 我们通过函数指针数组实现一个&#xff0c;图书管理系统的界面&#xff1a; #include <stdio.h> void doShowAllB…...

Linux学习之路 -- 文件 -- 文件描述符

前面介绍了与文件相关的各种操作&#xff0c;其中的各个接口都离不开一个整数&#xff0c;那就是文件描述符&#xff0c;本文将介绍文件描述符的一些相关知识。 目录 <1>现象 <2>原理 文件fd的分配规则和利用规则实现重定向 <1>现象 我们可以先通过prin…...

JDK动态代理和Cglib动态代理区别

1.如果目标类实现了接口&#xff0c;将会使用JDK动态代理&#xff0c;否则会使用Cglib动态代理; 2.JDK代理使用自己的字节码生成工具生成代理对象&#xff0c;而Cglib会使用ASM字节码生成工具去生成; 3.JDK动态代理是通过反射的方式去实现代理对象的所有方法&#xff0c;通过…...

牛客 | 字符金字塔

请打印输出一个字符金字塔&#xff0c;字符金字塔的特征请参考样例 #include <stdio.h> #include <string.h> using namespace std; int main() {char c;scanf("%c", &c);for (int i 1; i < (c - 64); i)//第一个循环决定了有多少行{//c:67 第三…...

【计算机科学速成课】笔记三——操作系统

文章目录 18.操作系统问题引出——批处理设备驱动程序多任务处理虚拟内存内存保护Unix 18.操作系统 问题引出—— Computers in the 1940s and early 50s ran one program at a time. 1940,1950 年代的电脑&#xff0c;每次只能运行一个程序 A programmer would write one at…...

用js代码实现贪吃蛇小游戏

js已经学了大部分了&#xff0c;现在就利用我所学的js知识试试做贪吃蛇小游戏吧 以下部分相关图片以及思路笔记均出自渡一陈老师的视频 首先制作简单的静态页面&#xff0c;添加贪吃蛇移动的背景和相关图片&#xff0c;比如开始游戏等等 将各个功能均封装在函数中&#xff0…...

微信小程序+esp8266温湿度读取

本文主要使用微信小程序显示ESP8266读取的温湿度并通过微信小程序控制LED灯。小程序界面如下图所示 原理讲解 esp8266 通过mqtt发布消息,微信小程序通过mqtt 订阅消息,小程序订阅后,就可以实时收到esp8266 传输来的消息。 个人可免费注册五个微信小程序账号,在微信小程序官…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

【git】把本地更改提交远程新分支feature_g

创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

LOOI机器人的技术实现解析:从手势识别到边缘检测

LOOI机器人作为一款创新的AI硬件产品&#xff0c;通过将智能手机转变为具有情感交互能力的桌面机器人&#xff0c;展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家&#xff0c;我将全面解析LOOI的技术实现架构&#xff0c;特别是其手势识别、物体识别和环境…...