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

【走迷宫】

题目

b94c7562f57448aa8b31b046531adf9f.png

DFS代码

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int matrix[N][N];
int n, m;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dis[N][N];
void dfs(int x, int y, int cnt)
{if(cnt > dis[n-1][m-1]) return;if(x == n-1 && y == m-1) return;for(int i = 0; i < 4; i++){int nx = x + dx[i], ny = y + dy[i];if(nx < 0 || ny < 0 || nx >= n || ny >= m || matrix[nx][ny]) continue;if(dis[nx][ny] > dis[x][y] + 1){dis[nx][ny] = dis[x][y] + 1;dfs(nx, ny, cnt+1);}}
}
int main()
{scanf("%d%d", &n, &m);for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){scanf("%d", &matrix[i][j]);}}memset(dis, 0x3f, sizeof dis);        dis[0][0] = 0;dfs(0, 0, 0);cout << dis[n-1][m-1];return 0;
}

优化:

1.if(cnt >= res) return; (较好)

2.if(dis[x][y] < cnt) return; (较好)
   else dis[x][y] = cnt;

3.         if(dis[nx][ny] > dis[x][y] + 1) (非常好)
        {
            dis[nx][ny] = dis[x][y] + 1;
            dfs(nx, ny, cnt+1);
        }

优化1+优化2都不如单用优化3

优化3可以替代优化2,同时可以不需要visited访问数组、cnt参数、res。

优化1可以和优化3搭配(需要cnt参数),效果最好,比单用优化3快一倍。为什么?

注意:优化2中和优化3中均不能加等号,前者会导致错误,后者会TLE。为什么?

 

 

 

BFS代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define f first
#define s secondconst int N = 110;
int g[N][N];
int n, m;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dis[N][N];
int bfs(int a, int b)
{queue<PII> q;q.push({a,b});dis[a][b] = 0;while(q.size()){PII u = q.front();q.pop();for(int i = 0; i < 4; i++){int nx = u.f + dx[i], ny = u.s + dy[i];if(nx >= 0 && ny >= 0 && nx < n && ny < m && !g[nx][ny] && dis[nx][ny] == -1){q.push({nx, ny});dis[nx][ny] = dis[u.f][u.s] + 1;}}}return dis[n-1][m-1];
}
int main()
{scanf("%d%d", &n, &m);for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){scanf("%d", &g[i][j]);}}memset(dis, -1, sizeof dis);cout << bfs(0, 0);return 0;
}

数组实现

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define f first
#define s secondconst int N = 110;
int g[N][N];
PII q[N * N];
int n, m;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dis[N][N];
int bfs(int a, int b)
{int h = 0, t = 0;q[0] = {a, b};dis[a][b] = 0;while(h <= t){auto u = q[h++];for(int i = 0; i < 4; i++){int nx = u.f + dx[i], ny = u.s + dy[i];if(nx >= 0 && ny >= 0 && nx < n && ny < m && !g[nx][ny] && dis[nx][ny] == -1){q[++t] = {nx, ny};dis[nx][ny] = dis[u.f][u.s] + 1;}}}return dis[n-1][m-1];
}
int main()
{scanf("%d%d", &n, &m);for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){scanf("%d", &g[i][j]);}}memset(dis, -1, sizeof dis);cout << bfs(0, 0);return 0;
}

 

 

相关文章:

【走迷宫】

题目 DFS代码 #include<bits/stdc.h> using namespace std; const int N 110; int matrix[N][N]; int n, m; int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1}; int dis[N][N]; void dfs(int x, int y, int cnt) {if(cnt > dis[n-1][m-1]) return;if(x n-1 &&a…...

linux(debian)迁移var数据到已分配逻辑卷的物理盘

文章目录 0 背景1 查看当前情况1.1 查看磁盘空间1.2 列出所有可用块设备的信息&#xff0c;而且还能显示他们之间的依赖关系1.3 查看可用磁盘1.4 查看卷组 2 卷组中创建逻辑卷3 创建文件系统4 创建临时文件夹并挂载&#xff0c;然后备份源文件5 修改开机挂载配置5.1 查看原配置…...

【产品那些事】什么是应用程序安全态势管理(ASPM)?

文章目录 前言当前应用安全(AppSec)推进遇到的问题关于ASPM的定义 为什么需要ASPM&#xff1a;B端客户核心需求ASPM产品关键策略理想状态下的ASPMASPM与CSPM的区别国内外产品参考 前言 随着现代软件开发实践的快速演变&#xff0c;特别是在敏捷开发和 DevOps 的推动下&#xf…...

cocosUI多分辨率适配

需求&#xff1a;由于各个设备的分辨率和尺寸并不一样&#xff0c;所以需要一套适配系统去很好的针对不同的设备分辨率或尺寸进行适配&#xff0c;以给玩家一个很好的游戏体验。 目前的主流适配方案 目前&#xff0c;针对不同设备的适配&#xff0c;主流的方案通常包括以下几种…...

无法加载到主类

说明&#xff1a;记录一次项目启动错误&#xff0c;如下&#xff1a; 错误信息&#xff1a;错误: 找不到或无法加载主类 com.hezy.App 原因: java.lang.ClassNotFoundException: com.hezy.App 解决&#xff1a;首先&#xff0c;在项目中勾选这个&#xff0c;显示target文件夹 …...

深入理解Kafka核心设计与实践原理_03

深入理解Kafka核心设计与实践原理_03 03_消费者3.1消费者与消费者组3.2客户端开发3.2.1 必要的参数配置3.2.2 订阅主题与分区 草稿 03_消费者 与生产者对应的是消费者&#xff0c;应用程序可以通过KafkaConsumer来订阅主题&#xff0c;并从订阅的主题中拉取消息。不过在使用Ka…...

MySQL- 覆盖索引

覆盖索引&#xff08;Covering Index&#xff09;是 MySQL 中的一种优化技术&#xff0c;它能够显著提高查询性能。在使用覆盖索引的情况下&#xff0c;查询操作只需要访问索引即可获取所需的数据&#xff0c;而不必再访问表的实际数据行&#xff08;即不需要回表&#xff09;。…...

JSON与EXL文件互转

功能&#xff1a;实现json到excel文件的相互转换(支持json多选版) 目的&#xff1a;编码与语言对应&#xff0c;方便大家使用 页面设计&#xff1a; 介绍&#xff1a; 1.选择文件栏目选择想要转换的文件 2.生成路径是转换后文件所在目录 3.小方框勾选与不勾选分别代表exl到…...

后台管理权限自定义按钮指令v-hasPermi

第一步:在src下面建立一个自定义指令文件,放自定义指令方法 permission.js文件: /*** v-hasPermi 操作权限处理*/import store from "/store";export default {inserted(el, binding) {const { value } binding;//从仓库里面获取到后台给的数组const permission s…...

【Python绘制散点图并添加趋势线和公式以及相关系数和RMSE】

在Python中&#xff0c;绘制散点图并添加趋势线&#xff08;通常是线性回归线&#xff09;、公式、以及相关系数&#xff08;Pearson Correlation Coefficient&#xff09;和均方根误差&#xff08;RMSE&#xff09;可以通过结合matplotlib用于绘图&#xff0c;numpy用于数学运…...

linux bridge VLAN

TP-Link 支持 Linux 桥接&#xff08;bridge&#xff09;和 VLAN 功能的产品主要包括其高端的交换机和一些企业级路由器&#xff1a; TP-Link JetStream 系列交换机&#xff1a; TL-SG3424: 24端口千兆交换机&#xff0c;支持 VLAN 和桥接。TL-SG3210: 24端口千兆管理型交换机&…...

Java进阶篇之深入理解多态的概念与应用

引言 在Java面向对象编程&#xff08;OOP&#xff09;中&#xff0c;多态&#xff08;Polymorphism&#xff09;是一个关键概念&#xff0c;它允许相同类型的对象在不同的场景中表现出不同的行为。多态不仅增强了代码的灵活性和可扩展性&#xff0c;还极大地提高了代码的可维护…...

Linux下的进程调度队列

我们在进程那一篇讲到了操作系统时间片轮换调度的概念 那么Linux下具体是怎么调度的&#xff1f;...

统计回归与Matlab软件实现上(一元多元线性回归模型)

引言 关于数学建模的基本方法 机理驱动 由于客观事物内部规律的复杂及人们认识程度的限制&#xff0c;无法得到内在因果关系&#xff0c;建立合乎机理规律的数学模型数据驱动 直接从数据出发&#xff0c;找到隐含在数据背后的最佳模型&#xff0c;是数学模型建立的另一大思路…...

【项目】基于Vue3.2+ElementUI Plus+Vite 通用后台管理系统

构建项目 环境配置 全局安装vue脚手架 npm install -g vue/cli-init打开脚手架图形化界面 vue ui创建项目 在图形化界面创建项目根据要求填写项目相关信息选择手动配置勾选配置项目选择配置项目然后我们就搭建完成啦&#x1f973;&#xff0c;构建可能需要一点时间&#xff0…...

随机生成 UUID

1、随机生成 UUID主方法 /*** 随机生成 UUID* param {*} len 生成字符串的长度* param {*} radix 生成随机字符串的长度**/export function uuid_(len 30, radix 20) {var chars 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz.split()var uuid [],ir…...

报名表EXCEL图片批量下载源码-CyberWinApp-SAAS 本地化及未来之窗行业应用跨平台架构

每次报名表都会包含大量照片&#xff0c;一张一张下载很慢 可以通过未来之窗开源平台架构 开开excel批量下载 实现代码也很简单 function 未来之窗下载(){ let 未来之窗地址 document.getElementById("batchurl").value; let 保存路径 document.getElementById(…...

SpringBoot 整合 Elasticsearch 实现商品搜索

一、Spring Data Elasticsearch Spring Data Elasticsearch 简介 Spring Data Elasticsearch是Spring提供的一种以Spring Data风格来操作数据存储的方式&#xff0c;它可以避免编写大量的样板代码。 常用注解 常用注解说明如下&#xff1a; 注解名称 作用 参数说明 Docu…...

计算机毕业设计 助农产品采购平台 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

&#x1f34a;作者&#xff1a;计算机编程-吉哥 &#x1f34a;简介&#xff1a;专业从事JavaWeb程序开发&#xff0c;微信小程序开发&#xff0c;定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事&#xff0c;生活就是快乐的。 &#x1f34a;心愿&#xff1a;点…...

Django后台数据获取展示

​ 续接Django REST Framework&#xff0c;使用Vite构建Vue3的前端项目 1.跨域获取后台接口并展示 安装Axios npm install axios --save 前端查看后端所有定义的接口 // 访问后端定义的可视化Api接口文档 http://ip:8000/docs/ // 定义的学生类信息 http://ip:8000/api/v1…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

PostgreSQL——环境搭建

一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在&#xff0…...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下&#xff1a; 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载&#xff0c;下载地址&#xff1a;https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...

OD 算法题 B卷【正整数到Excel编号之间的转换】

文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的&#xff1a;a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...

通过MicroSip配置自己的freeswitch服务器进行调试记录

之前用docker安装的freeswitch的&#xff0c;启动是正常的&#xff0c; 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...

9-Oracle 23 ai Vector Search 特性 知识准备

很多小伙伴是不是参加了 免费认证课程&#xff08;限时至2025/5/15&#xff09; Oracle AI Vector Search 1Z0-184-25考试&#xff0c;都顺利拿到certified了没。 各行各业的AI 大模型的到来&#xff0c;传统的数据库中的SQL还能不能打&#xff0c;结构化和非结构的话数据如何和…...

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态

前言 在人工智能技术飞速发展的今天&#xff0c;深度学习与大模型技术已成为推动行业变革的核心驱动力&#xff0c;而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心&#xff0c;系统性地呈现了两部深度技术著作的精华&#xff1a;…...