搜索与图论:宽度优先搜索

搜索与图论:宽度优先搜索

    • 题目描述
    • 参考代码

题目描述

在这里插入图片描述
输入样例

5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

输出样例

8

参考代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;const int N = 110;typedef pair<int, int> PII;int n, m;
int g[N][N];    // 存储地图
int d[N][N];    // 每一个点到起点的距离
PII q[N * N], Prev[N][N];int bfs()
{int hh = 0, tt = 0;q[0] = {0, 0};memset(d, -1, sizeof d);d[0][0] = 0;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 < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1){d[x][y] = d[t.first][t.second] + 1;Prev[x][y] = t;q[++ tt] = {x, y};}}}int x= n - 1, y = m - 1;while (x || y){cout << x << ' ' << y << endl;auto t = Prev[x][y];x = t.first, y = t.second;}return d[n - 1][m - 1];
}int main()
{cin >> n >> m;for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)cin >> g[i][j];cout << bfs() << endl;return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/345221.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

course-nlp——8-translation-transformer

本文参考自https://github.com/fastai/course-nlp。 注意力机制和 Transformer Nvidia AI 研究员 Chip Huyen 写了一篇很棒的文章《Top 8 trends from ICLR 2019》&#xff0c;其中的趋势之一是 RNN 正在失去研究人员的青睐。 这是有原因的&#xff0c;RNN 可能很麻烦&#…

course-nlp——5-nn-imdb

本文参考自https://github.com/fastai/course-nlp。这部分是fastai1.0版本的教程&#xff0c;由于现在fastai2.0重构的改变非常大&#xff0c;所以文中的很多api都变了&#xff0c;由于学习目的并不是熟练掌握fastai&#xff0c;因此这里就简单的存一下&#xff0c;本文是用IMD…

数据库 | 关系数据库设计

第七章 1.简述数据库的设计阶段&#xff1f;&#xff08;简要回答数据库设计步骤&#xff1f;&#xff09;&#xff08;&#xff08;数据库设计有哪几个阶段&#xff1f;&#xff09; 需求分析、概念结构设计、逻辑结构设计、物理结构设计、数据库的实施、数据库的运行和维护…

美团大规模KV存储挑战与架构实践--图文分析

美团大规模KV存储挑战与架构实践–图文分析 原作者&#xff1a;美团技术团队 原文链接&#xff1a;https://tech.meituan.com/2024/03/15/kv-squirrel-cellar.html 1 美团 KV 存储发展历程 第一代&#xff1a;使用Memcached 什么是一致性哈希&#xff1f; 哈希&#xff1a…

Elasticsearch 认证模拟题 - 17

这两道题目非常具有代表性&#xff0c;分别是跨集群复制和跨集群检索&#xff0c;需要相应的 许可 这里在虚拟机上搭建集群完成这两道题目&#xff0c;这里补充一下 elasticsearch 和 kibana 的配置文件 # elasticsearch.yml cluster.name: cluster2 node.name: cluster2-node…

【python解决】查询报%d format: a number is required, not str问题

【Python解决】查询报%d format: a number is required, not str问题 在Python中&#xff0c;字符串格式化是一种常见的操作&#xff0c;用于创建包含变量的字符串。如果你在使用%操作符进行格式化时遇到了%d format: a number is required, not str的错误&#xff0c;这意味着…

Java Web学习笔记20——Ajax-Axios

Axios&#xff1a; 介绍&#xff1a;Axios对原生的Ajax进行封装&#xff0c;简化书写&#xff0c;快速开发。 官网&#xff1a;https://www.axios-http.cn Axios 入门&#xff1a; {}是Js的对象。 get的请求参数是在URL后面&#xff1f;和相关参数值。 post的请求参数是在请…

素颜个人引导页源码

源码介绍 素颜个人引导页源码&#xff0c;源码由HTMLCSSJS组成&#xff0c;记事本打开源码文件可以进行内容文字之类的修改&#xff0c;双击html文件可以本地运行效果&#xff0c;也可以上传到服务器里面&#xff0c;重定向这个界面 效果预览 源码下载 素颜个人引导页源码

IIS7整合Tomcat9服务器,并搭建ASP+PHP+JSP完整运行环境

本文以Windows Vista系统为例&#xff0c;详细讲解IIS7整合Tomcat服务器&#xff0c;同时支持ASPPHPJSP三种Web动态网页技术的方法。 Vista系统自带的IIS版本为7.0&#xff0c;能安装的IE浏览器的最高版本为IE9。IE9也是Vue2前端框架支持的最低浏览器版本。 【准备工作】 去微…

k8s——pod控制器

一、pod控制器定义 Pod控制器&#xff0c;又称之为工作负载&#xff08;workload&#xff09;&#xff0c;是用于实现管理pod的中间层&#xff0c;确保pod资源符合预期的状态&#xff0c;pod的资源出现故障时&#xff0c;会尝试进行重启&#xff0c;当根据重启策略无效&#xf…

「动态规划」打家劫舍的变形题,你会做吗?

213. 打家劫舍 IIhttps://leetcode.cn/problems/house-robber-ii/description/ 你是一个专业的小偷&#xff0c;计划偷窃沿街的房屋&#xff0c;每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈&#xff0c;这意味着第一个房屋和最后一个房屋是紧挨着的。同时&#x…

QT Udp广播实现设备发现

测试环境 本文选用pc1作为客户端&#xff0c;pc2&#xff0c;以及一台虚拟机作为服务端。 pc1,pc2(客户端&#xff09;: 虚拟机&#xff08;服务端)&#xff1a; 客户端 原理&#xff1a;客户端通过发送广播消息信息到ip:255.255.255.255(QHostAddress::Broadcast),局域网…

Tensorflow入门实战 P03-天气识别

目录 1、完整代码 2、运行结果 2.1 查看20张图片 2.2 程序运行 2.3 运行结果 3、小结 ① 代码运行过程中有报错&#xff1a; ② 修改代码如下&#xff1a; ③ 分析原因&#xff1a; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&…

STM32H750启动和内存优化(分散加载修改)

前些日子有个朋友一直给我推荐STM32H750这款芯片&#xff0c;说它的性价比&#xff0c;说它多么多么好。于是乎&#xff0c;这两天试了试&#xff0c;嚯&#xff0c;真香&#xff01;我们先看看基本配置 这里简单总结下&#xff0c;cortex-m7内核&#xff0c;128k片内flash …

k8s挂载配置文件(通过ConfigMap方式)

一、ConfigMap简介 K8s中的ConfigMap是一种用于存储配置数据的API对象&#xff0c;属于Kubernetes中的核心对象。它用于将应用程序的配置信息与容器镜像分离&#xff0c;以便在不重新构建镜像的情况下进行配置的修改和更新。ConfigMap可以存储键值对、文本文件或者以特定格式组…

[Vue-常见错误]浏览器显示Uncaught runtime errors

文章目录 错误描述正确写法具体如下 错误描述 当前端代码发生错误时&#xff0c;浏览器中出现以下错误提示。 正确写法 显然这不是我们所期望的&#xff0c;在vue.config.js中配置如下设置关闭Uncaught runtime errors显示 devServer: {client: {overlay: false}具体如下 …

UltraEditUEStudio软件最新版下载及详细安装教程

UEStudio简介&#xff1a; UEStudio建立在上文本编辑器UltraEdit的功能基础上&#xff0c;并为团队和开发人员提供了其他功能&#xff0c;例如深度Git集成。您可以直接在UEStudio中克隆&#xff0c;签出&#xff0c;更新&#xff0c;提交&#xff0c;推入/拉入等操作&#xff…

【WEB前端2024】3D智体编程:乔布斯3D纪念馆-第37课-自动切换纹理

【WEB前端2024】3D智体编程&#xff1a;乔布斯3D纪念馆-第37课-自动切换纹理 使用dtns.network德塔世界&#xff08;开源的智体世界引擎&#xff09;&#xff0c;策划和设计《乔布斯超大型的开源3D纪念馆》的系列教程。dtns.network是一款主要由JavaScript编写的智体世界引擎&…

后台管理系统排序混乱,分页出现重复条例

检查了接口和请求参数都没有问题。 查询数据库发现是排序字段create_time 都相同导致的。没有区分度。 解决方案 按照唯一id排序 避免create_time 大批量相同 order by create_time &#xff0c;xxx 两个排序字段