844. 走迷宫 典bfs

AC代码:

#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;
const int N =110;

int mp[N][N];
int sx,sy;
bool vis[N][N];
struct node{
	int x,y;
};
int n,m;

int dx[] = {1,-1,0,0};
int dy[] = {0,0,-1,1};
//int cnt;
int path[N][N];
 
void bfs(int xx,int yy){
	queue<node> q;
	q.push({xx,yy});
	vis[xx][yy] = true;
	path[xx][yy] = 0;
	
	while(!q.empty()){
		node temp = q.front();
		q.pop();
		
		for(int i=0;i<4;i++){
			int nx = dx[i] + temp.x;
			int ny = dy[i] + temp.y;
			
			if(nx > n || nx < 1 || ny > m || ny < 1) continue;
			if(vis[nx][ny]) continue;
			if(mp[nx][ny] == 1) continue;
			if(!vis[nx][ny] && mp[nx][ny] == 0){
				vis[nx][ny] = true;
			//	cnt++;//这是算能到达的点 
				path[nx][ny] = path[temp.x][temp.y] + 1;
				q.push({nx,ny});
			}
			if(nx == n && ny == m) {
			//	printf("%d",cnt);
			printf("%d",path[n][m]);
				return ;
			}
		}
	}
	return ;
			
}
int main()
{
	scanf("%d%d",&n,&m);
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int c;
			scanf("%d",&c);
			mp[i][j] = c;			
		}
	}
	if(n==1 && m==1){
	    printf("0");
	}
	else bfs(1,1);
	return 0;
}

结果:

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

2024年热门游泳耳机推荐!公认最佳的4大游泳耳机分享,好用不贵

随着科技的发展&#xff0c;游泳运动已经不仅仅是一项健身活动&#xff0c;更是一种生活方式。在游泳过程中&#xff0c;音乐的陪伴能够让我们更好地享受这项运动&#xff0c;同时也能提高我们的游泳效果。因此&#xff0c;选择一款适合自己的游泳耳机显得尤为重要。 然而&…

嵌入式和 Java 走哪条路?

最近看到一个物联网大三学生的疑问&#xff0c;原话如下&#xff1a; 本人普通本科物联网工程专业&#xff0c;开学大三&#xff0c;现在就很迷茫&#xff0c;不打算考研了&#xff0c;准备直接就业&#xff0c;平时一直在实验室参加飞思卡尔智能车比赛&#xff0c;本来是想走嵌…

BRICK POP展示了有趣的链上游戏玩法与奖励

新游戏BRICK POP将Sui区块链技术与低Gas费用&#xff0c;以及我们在Web3游戏开发方面的专业知识无缝结合。通过充分利用Sui和我们自己的INNO平台的优势&#xff0c;BRICK POP为玩家提供了一个融合了前沿技术和引人入胜游戏的沉浸式游戏体验。BRICK POP游戏设计为实时交易和高用…

配置文件 application properties

配置文件 application properties 1 参数交由配置文件集中管理 Value(“${}”)用于外部配置的属性注入 在之前编写的程序中进行文件上传时&#xff0c;需要调用AliOSSUtils工具类&#xff0c;将文件上传到阿里云OSS对象存储服务当中。而在调用工具类进行文件上传时&#xff0c…

JaveSE—IO流详解:对象输入输出流(序列化及反序列化)

一. 基础理论知识 &#x1f4cc;怎么理解对象输入输出流 &#xff1f; ○ 把java中的对象输出到文件中&#xff0c;从文件中把对象输入到程序中. &#x1f4cc;为什么要这样做(目的) &#xff1f; 当我们创建一个对象时, 如new Student( "小张",20 ); 数据存储在…

【Ucore操作系统】8. 并发

文章目录 【 0. 引言 】0.1 线程定义0.2 同步互斥 【 1. 内核态的线程管理 】1.1 线程概念1.2 线程模型与重要系统调用1.2.1 线程创建系统调用1.2.2 等待子线程系统调用1.2.3 进程相关的系统调用 1.3 应用程序示例1.3.1 系统调用封装1.3.2 多线程应用程序 – threads 1.4 线程管…

STL中 function 源码解析

1. function 本文基于 GCC 9.4 function 的作用就是将各种仿函数的调用统一起来&#xff1b; 1.1 类中非静态成员函数指针为什么是16字节 auto cptr &A::myfunc; 类中非静态成员函数 &#xff0c;其类型为 void (A::*)(int) auto rptr print_num; 普通函数对应汇…

git clone 后如何 checkout 到 remote branch

what/why 通常情况使用git clone github_repository_address下载下来的仓库使用git branch查看当前所有分支时只能看到master分支&#xff0c;但是想要切换到其他分支进行工作怎么办❓ 其实使用git clone下载的repository没那么简单&#x1f625;&#xff0c;clone得到的是仓库…

23种设计模式之创建型模式 - 单例模式

文章目录 一、单例模式1.1单例模式定义1.2 单例模式的特点 二、实现单例模式的方式2.1 饿汉式2.2 懒汉式2.3 双重检查锁&#xff1a;2.4 静态内部类2.5 枚举实现&#xff08;防止反射攻击&#xff09;&#xff1a; 一、单例模式 1.1单例模式定义 单例模式确保系统中某个类只有…

docker学习笔记 四-----docker基本使用方法

基础命令奉上&#xff1a; 1、docker命令查询方法 docker --help 获取docker命令帮助 docker search --help 查询docker 子命令search的帮助 2、查询镜像 查询镜像 docker search 192.168.206.100:5000/mysql 查询指定服务器指定镜像 docker search mysql …

Redis入门到实战-第二十弹

Redis实战热身Time series篇 完整命令参考官网 官网地址 声明: 由于操作系统, 版本更新等原因, 文章所列内容不一定100%复现, 还要以官方信息为准 https://redis.io/Redis概述 Redis是一个开源的&#xff08;采用BSD许可证&#xff09;&#xff0c;用作数据库、缓存、消息代…

Redis入门到实战-第十六弹

Redis实战热身Cuckoo filter篇 完整命令参考官网 官网地址 声明: 由于操作系统, 版本更新等原因, 文章所列内容不一定100%复现, 还要以官方信息为准 https://redis.io/Redis概述 Redis是一个开源的&#xff08;采用BSD许可证&#xff09;&#xff0c;用作数据库、缓存、消息…

Transformer的前世今生 day10(Transformer编码器

前情提要 ResNet&#xff08;残差网络&#xff09; 由于我们加更多层&#xff0c;更复杂的模型并不总会改进精度&#xff0c;可能会让模型与真实值越来越远&#xff0c;如下&#xff1a; 我们想要实现&#xff0c;加上一个层把并不会让模型变复杂&#xff0c;即没有它也没关系…

【启发式算法】同核分子优化算法 Homonuclear Molecules Optimization HMO算法【Matlab代码#70】

文章目录 【获取资源请见文章第4节&#xff1a;资源获取】1. 算法简介2. 部分代码展示3. 仿真结果展示4. 资源获取 【获取资源请见文章第4节&#xff1a;资源获取】 1. 算法简介 同核分子优化算法&#xff08;Homonuclear Molecules Optimization&#xff0c;HMO&#xff09;是…

数据结构面试常见问题之串的模式匹配(KMP算法)系列-大师改进

&#x1f600;前言 KMP算法是一种改进的字符串匹配算法&#xff0c;由D.E.Knuth&#xff0c;J.H.Morris和V.R.Pratt提出&#xff0c;因此人们称它为克努特—莫里斯—普拉特操作&#xff08;简称KMP算法&#xff09; KMP算法的优势: 提高了匹配效率&#xff0c;时间复杂度为O(m…

力扣面试150 移除元素 双指针

Problem: 27. 移除元素 思路 &#x1f468;‍&#x1f3eb; 三叶题解 复杂度 时间复杂度: O ( n ) O(n) O(n) 空间复杂度: O ( 1 ) O(1) O(1) Code class Solution {public int removeElement(int[] nums, int val) {int j nums.length - 1;for (int i 0; i < j;…

Netty服务端基本启动流程源码刨析

前言: 希望看这篇文章之前对Java Nio编程比较熟悉&#xff0c;并有用过Netty开发简单代码 服务端代码 先大致说一下NioEventLoopGroup组件的作用&#xff0c;可以把它看是作内部维护了一个NioEventLoop数组的对象&#xff0c;它的构造方法的参数用来指定维护数组的大小。NioEve…

快速上手Spring Cloud 十:Spring Cloud与微前端

快速上手Spring Cloud 一&#xff1a;Spring Cloud 简介 快速上手Spring Cloud 二&#xff1a;核心组件解析 快速上手Spring Cloud 三&#xff1a;API网关深入探索与实战应用 快速上手Spring Cloud 四&#xff1a;微服务治理与安全 快速上手Spring Cloud 五&#xff1a;Spring …