【算法入门&搜索法】走迷宫|单源最短路径1

这篇具有很好参考价值的文章主要介绍了【算法入门&搜索法】走迷宫|单源最短路径1。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

✅作者简介:热爱后端语言的大学生,CSDN内容合伙人
✨精品专栏:C++面向对象
🔥系列专栏:算法百炼成神

🔥前言

本专栏收录的均为牛客网的算法题目,内含链表、双指针、递归、动态规划、基本数据结构等算法思想的具体运用。牛客网不仅有大量的经典算法题目,也有大厂的面试真题,面试、找工作完全可以来这里找机会。此外,网站内的编码主题多样化,调试功能可运用性强,可谓是非常注重用户体验。这么好的免费刷题网站还不快入手吗,快去注册开启算法百炼成神之路吧!

1、AB20 走迷宫

广度优先算法实现,充分利用邻接矩阵

题目链接:走迷宫

利用搜索算法完成走迷宫c#,# 经典算法的C++实现,算法,图论,c++利用搜索算法完成走迷宫c#,# 经典算法的C++实现,算法,图论,c++

1.1、解题思路

本题求的是起点到最终点所需要走的最小步数,那就必然少不了邻接矩阵的使用与点移动的逻辑,而整体上是广度优先算法来实现,需要利用队列:

  • 根据网格大小确定邻接矩阵的大小并初始化全都未被访问:
    • 用标记数组flag来记录位置是否被访问过
  • 使用对组pair表示横纵坐标:
    • 纵坐标正方向用第一个变量表示,横坐标正方向用第二个变量表示
    • 相当于点(x,y)在第四象限的移动,x在竖轴,y在横轴移动
  • 每个位置都要进行四周的移动,因此要设计移动逻辑:
    • 不妨定义两个数组,通过-101 的组合确定移动方向
    • 访问到未被访问的坐标就把其入队并将布尔值设为true,避免重复访问
      • 该点的距离根据起始点的距离进行加一,终点的距离就是最终结果

1.2、代码实现与注释

本题源码:

#include <iostream>
#include <cstring> // 引入memset函数的头文件
#include <queue>
using namespace std;
queue<pair<int, int>> q;
const int N = 1001;
int  w[N][N]; // 代表矩阵中起点到各点最短距离
char a[N][N]; // 用来输入*或者. (障碍和通路)
bool b[N][N]; // 标志位,记录坐标是否被访问过

int xs, ys, xt, yt; // s 代表起始点,t代表终点
int n, m;

// 注意dx和dy数组存放的数据要对应,代表着上下左右的移动方向
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

// 核心算法:广度优先
int bfs() {
    memset(w, -1, sizeof(w)); // 初始距离全部设为-1
    memset(b, 0, sizeof(b));  // 初始邻接矩阵全部设为未访问
    b[xs][ys] = 1;
    q.push(make_pair(xs, ys));
    while (!q.empty()) {
        int x1, y1;
        x1 = q.front().first, y1 = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int x2 = x1 + dx[i], y2 = y1 + dy[i];
            if (x2 >= 1 && x2 <= n && y2 >= 1 && y2 <= m && b[x2][y2] == false &&
                    a[x2][y2] == '.') {
                b[x2][y2] = true;
                w[x2][y2] = w[x1][y1] + 1;
                q.push(make_pair(x2, y2));
            }
        }
    }
    return w[xt][yt] + 1;
}

int main() {
    cin >> n >> m;
    cin >> xs >> ys >> xt >> yt;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    if (bfs() == 0)
        cout << "-1" << endl;
    else
        cout << bfs();
    return 0;
}

重要注释:

  • 将各种矩阵与变量定义在 main 函数以外,这样可以使用无参的bfs函数,省去了传参过程
  • memset 函数常用于给存储空间快速赋值,比较典型的就是配合数组进行初始化
  • 坐标方面的细节:
    • (-1,0)、(1,0)、(0,-1)、(0,1)分别表示上移、下移、左移、右移

2、AB19 【模板】单源最短路1

之前发过单源最短路2,最短路1与之的区别在于边的权值都是1

文章链接:图论入门

2.1、单源最短路汇总

边权值相同的解题源码:

#include <iostream>
#include<climits> // 使用INT_MAX所需要引入的头文件
const int MAX = 5001;
using namespace std;


int main() {
    int G[MAX][MAX];
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            G[i][j] = INT_MAX;
        }
    }
    int n, m;
    cin >> n >> m;
    int u, v;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v;
        G[u][v] = 1;
        G[v][u] = 1;
    }
    bool flag[MAX];
    int dist[MAX];
    for (int i = 1; i < MAX; i++) {
        dist[i] = G[1][i];
        flag[i] = false;
    }

    dist[1] = 0;
    flag[1] = true;
    for (int i = 2; i < MAX; i++) {
        int temp = INT_MAX, index = 1;
        for (int j = 1; j < MAX; j++) {
            if (flag[j] == false && dist[j] < temp) {
                temp = dist[j];
                index = j;
            }
        }
        if (index != 1) {
            flag[index] = true;
        }
        for (int i = 2; i < MAX; i++) {
            if (flag[i] == false && G[index][i] != INT_MAX) {
                if (G[index][i] + dist[index] < dist[i]) {
                    dist[i] = G[index][i] + dist[index];
                }
            }
        }
    }
    if (dist[n] == INT_MAX) {
        cout << -1;
    } else {
        cout << dist[n];
    }
    return 0;
}


上面链接中有权值不同的单源最短路详解,思路几乎一致,大家可以再去温习一波,这类题型也算是图论中的典型算法题目了。文章来源地址https://www.toymoban.com/news/detail-777412.html

到了这里,关于【算法入门&搜索法】走迷宫|单源最短路径1的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法提高-图论-单源最短路的综合应用

    多次dijkstra求每个点到其它点的最短距离, 此时相当于建好了一张图,每个点之间的最短距离都知道了,接下来dfs搜一下怎么走最短即可 一篇博客解释了为什么一个正向建图求最小值,反向建图求最大值 根本思想是保证1到n的买卖是连通的

    2024年02月11日
    浏览(75)
  • C++算法:单源最短路径Dijkstra

    如果你有一份北京地图,想从中关村走到三元桥,那么怎样能找出实现这一目的的最短路径呢?一种可能的方法就是将这两点之间所有的路线都找出来,然后求出每条路线的距离,找出最短的路线。但是仔细想想我们就会发现这种办法几乎是不可行的,因为这样的路线太多了,

    2024年02月09日
    浏览(45)
  • 算法提高-图论-单源最短路的扩展应用

    多源点单终点最短路建图: 创建虚拟源点(创建虚拟源点的时候以是spfa为例 可以在建图的时候建出来,也可以在spfa这直接入队,也是虚拟源点的意思) 反向建图变成单源点多终点,然后遍历终点的dist即可找出最短路 这题挺简单的就不详细说了,主要是第一次遇到计数问题

    2024年02月16日
    浏览(48)
  • 迪杰斯特拉算法 – 图的单源最短路径

    迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。迪杰斯特拉算法采

    2024年02月05日
    浏览(42)
  • 图论算法基础:单源最短路径Dijkstra算法分析

    在 有向带权图 中给定一个起始顶点(源点),Dijkstra算法可以求出 所有其他顶点 到源点的最短路径,Dijkstra算法 不能用于同时含有正负权值的边的图 Source 顶点集合:已经确定 到源点的最短路径 的顶点就会加入 Source 集合中, Source 集合初始时只有源点 dist 数组:用于记录每个顶点到

    2024年02月11日
    浏览(44)
  • 算法提高-图论-单源最短路的建图方式

    建图 找出一个牧场,它到其他牧场的距离之和最小 我是这么理解的,djsktra是一个贪心的思想,加法里面不能加负数我就不说了 求乘法最大值的时候为什么边权必须0-1,因为在乘法最大值里面有一个边权大于1的话那不就等价于求加法最小值的时候有一个边权为负数的么,d

    2024年02月08日
    浏览(45)
  • 贝尔曼福特算法——负权值单源最短路径

    title: 贝尔曼福特算法——负权值单源最短路径 date: 2023-05-16 11:42:26 tags: 数据结构与算法 **问题:**具有负权值非环图的单源最短路径算法 git地址:https://github.com/944613709/HIT-Data-Structures-and-Algorithms 对图中的边进行V-1轮遍历,对所有的边松弛(对每条边v1-v2,如果d[v2]+Weight(v1-v2)

    2024年02月14日
    浏览(38)
  • Dijkstra算法——单源最短路径(指定一个节点(源点)到其余各个顶点的最短路径)

    国庆期间,小明打算从1号城市出发,在五天假期中分别去往不同的城市(2,3,4,5,6)旅游,为减轻负担,他想要知道1号城市到各个城市之间的最短距离。 现在需要设计一种算法求得源点到任意一个城市之间的最短路径。该问题的求解也被称为“单源最短路径”。 在所有

    2024年02月03日
    浏览(55)
  • C++ | 数据结构与算法 | 单源最短路径 | Dijkstra && Bellman Ford

    (关于代码实现的图结构,可以看图结构的实现这篇文章) Dijkstra的实现与Prim的实现相似,两者都是通过贪心思想实现,它们有什么不同呢?首先Prim算法是针对无向图的最小生成树的,而Dijkstra算法是针对 有向图 的最短路径生成。一个的目的是连接图中的所有顶点,生成一

    2024年02月03日
    浏览(49)
  • 【数据结构】最小生成树(Prim算法,普里姆算法,普利姆)、最短路径(Dijkstra算法,迪杰斯特拉算法,单源最短路径)

    问题解答 (1)最小生成树(Minimal Spanning Tree)的定义 生成树的代价 :设 G ( V , E ) G(V,E) G ( V , E ) 是一个无向连通网图,生成树上 各边的权值之和 称为 生成树的代价 。 最小生成树 :在图 G G G 所有生成树中, 代价最小的生成树 为 最小生成树 。 (2)最小生成树(MST)的性

    2024年02月11日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包