C++广搜例题代码加讲解(1)

news/2024/7/8 3:31:48 标签: c++, 算法, 数据结构

        题目描述:在一个n*m大小的网格中,1代表障碍物,0代表可以通过,从左上角走到右下角,每次只能上下左右移动一格,求最短路径长度。

示例输入:

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

示例输出:

13

#include <iostream>
#include <queue>

using namespace std;

const int N = 110;

int n, m;
int g[N][N]; // 存储地图(0表示可以通过,1表示障碍物)
int dis[N][N]; // 存储每个位置到起点的最短路径长度,初始化为-1
int dx[4] = {-1, 0, 1, 0}; // 四个方向的x坐标变化
int dy[4] = {0, 1, 0, -1}; // 四个方向的y坐标变化

struct Node { // 存储每个位置的坐标
    int x, y;
};

// 判断当前位置是否可以走(不越界且不是障碍物且之前没有被访问过)
bool check(int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= m || g[x][y] == 1 || dis[x][y] != -1) {
        return false;
    }
    return true;
}

void bfs() {
    queue<Node> q;
    q.push({0, 0});
    dis[0][0] = 0; // 

http://www.niftyadmin.cn/n/5112581.html

相关文章

KubeSphere一键安装部署K8S集群(单master节点)-亲测过

1. 基础环境优化 hostnamectl set-hostname master1 && bash hostnamectl set-hostname node1 && bash hostnamectl set-hostname node2 && bashcat >> /etc/hosts << EOF 192.168.0.34 master1 192.168.0.45 node1 192.168.0.209…

面向对象【构造器】

文章目录 构造器定义构造器的作用构造器的使用说明无参构造器带参数的构造器构造器的重载使用构造器创建对象 总结 构造器定义 构造器是一种特殊类型的方法&#xff0c;它与类同名&#xff0c;没有返回值&#xff0c;并且用于在创建对象时执行初始化操作。构造器的名称必须与类…

ARM映像文件组成

引言 ARM编译器将各种源文件&#xff08;汇编文件、C语言程序文件、C语言程序文件&#xff09;编译生成ELF格式的目标文件&#xff08;后缀为.o文件&#xff0c;以下将目标文件简称为.o文件&#xff09;&#xff0c;.o文件经过连接器&#xff0c;和C/C运行时库一起编译生成ELF格…

某验四代滑块验证码逆向分析

逆向目标 目标&#xff1a;某验四代滑块验证码&#xff0c;w 参数逆向主页&#xff1a;aHR0cHM6Ly9ndDQuZ2VldGVzdC5jb20v加密算法&#xff1a;RSA、AES 通讯流程 验证码流程分析 进入网页后&#xff0c;打开开发者人员工具进行抓包&#xff0c;点击滑动拼图验证&#xff0c…

用 pytorch 训练端对端验证码识别神经网络并进行 C++ 移植

文章目录 前言安装安装 pytorch安装 libtorch安装 opencv&#xff08;C&#xff09; 准备数据集获取训练数据下载标定 编码预分析 数据集封装格式 神经网络搭建神经网络训练神经网络测试神经网络预测C 移植模型转换通过跟踪转换为 Torch Script通过注解转换为 Torch Script 编写…

windows系统kettle9.3一键安装启动

程序下载、解压 通过百度网盘下载&#xff0c;直接解压即可 解压之后 双击运行 程序路径 pdi-ce-9.3.0.0-428一键安装启动\pdi-ce-9.3.0.0-428\data-integration

散列表:Word文档中的单词拼写检查功能是如何实现的?

文章来源于极客时间前google工程师−王争专栏。 一旦我们在Word里输入一个错误的英文单词&#xff0c;它就会用标红的方式提示“编写错误”。Word的这个单词拼写检查功能&#xff0c;虽然很小但却非常实用。这个功能是如何实现的&#xff1f; 散列别&#xff08;Hash Table&am…

Go构建者模式

构建者模式是一种创建型设计模式&#xff0c;用于构建复杂的对象。它可以确保在一个 struct 有多个构造函数参数时依旧能保持代码的可读性与清晰性。 1、链式写法 type computer struct {cpu stringarm string }func NewComputer() *computer {return &computer{} }func …