开发者社区> 辰Chen> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

最短路模型(一)

简介: 复习acwing算法提高课的内容,本篇为讲解算法:最短路模型,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上。
+关注继续查看

文章目录

前言

一、最短路

二、例题,代码

AcWing 1076. 迷宫问题

本题分析

AC代码

AcWing 188. 武士风度的牛

本题分析

AC代码

AcWing 1100. 抓住那头牛

本题分析

AC代码

三、时间复杂度


前言

复习acwing算法提高课的内容,本篇为讲解算法:最短路模型,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上。


一、最短路

我们在算法基础部分已经说明了几种计算最短路的方式:Dijkstra,bellman-ford,spfa,Floyd,我们也可以通过bfs去计算最短路(边权一样),在这里的最短路模型中我们用到的核心思想就是bfs中的思想


二、例题,代码

AcWing 1076. 迷宫问题

本题链接:AcWing 1076. 迷宫问题

本博客提供本题截图:

image.png

image.png


本题分析

核心思路是不会变的,都是bfs的模板,下面来说说细节,如何去记录一条路径:利用pre数组,pre数组存储的是当前状态是由哪一个状态转变过来的,这样每次记录前一个点,反推回去就可以得到整条路径,对于本题,起始点(0,0),终点(n - 1, n - 1)是已经固定好的,我们要求出一条从起点到终点的最短路径,我们知道pre数组是倒着存储的(存的是前一个状态),所以我们可以倒着进行bfs,就是把(n - 1,n - 1)当成起点,(0,0)当成终点去进行bfs,这样我们就不需要把pre翻转进行输出,同时,我们可以发现,相比较与原先的bfs,本题的AC代码中居然没有bool数组st去进行标记是否搜过这个点,其实是有的,只不过我们把st判重数组和pre记录路径的数组进行了合并,我们初始化pre数组,让其内所有元素的值为-1,因为pre会被更新,所以如果这个点的pre的值为-1,证明没有被更新过,就可以加入到我们的队列中,反之证明被更新过,根据最短路bfs的性质,对于这种情况我们直接continue


AC代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1010, M = N * N;

PII q[M];
PII pre[N][N];
int g[N][N];
int n;

void bfs(int x1, int y1)
{
    memset(pre, -1, sizeof pre);
    
    int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};
    
    int hh = 0, tt = 0;
    q[0] = {x1, y1};
    while (hh <= tt)
    {
        auto t = q[hh ++];
        
        for (int i = 0; i < 4; i ++ )
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= n) continue;
            if (g[a][b]) continue;
            if (pre[a][b].x != -1) continue;
            
            q[ ++ tt] = {a, b};
            pre[a][b] = t;
        }
    }
}

int main()
{
    scanf("%d", &n);
    
    for (int i = 0; i < n; i ++ ) 
        for (int j = 0; j < n; j ++ ) 
            scanf("%d", &g[i][j]);
            
    bfs(n - 1, n - 1);
    
    PII end{0, 0};
    
    while (true)
    {
        printf("%d %d\n", end.x, end.y);
        if (end.x == n - 1 && end.y == n - 1) break;
        end = pre[end.x][end.y];
    }
    
    return 0;
}



版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
KANO模型
KANO模型由东京理工大学教授狩野纪昭(Noriaki Kano)发明,其用于分析用户对于各类需求的排名偏好情况,其在企业产品需求调研,市场研究中有着广泛的应用。
43 0
电路模型和电路定律(Ⅱ)
只适用于 线性电阻 (R为常数),注:欧姆定律范围非常狭窄只限于线性电阻当中。 如电阻上的 电压 与 电流 参考方向非关联的话,公式中应该是为负号。 说明线性电阻式无记忆、双向性的元
33 0
电路模型和电路定律(Ⅲ)
独立源电压或电流,由电源本身来决定的,与电路中其它电压、电流无关,而受控源电压或电流由控制量决定的。 独立源在电路中起到"激励"作用,在
38 0
模型融合
模型融合:voting、averaging、bagging、stacking、boosting 首先简单介绍了各个模型融合方法,主要讲解Adaboost算法。
1727 0
+关注
辰Chen
CSDN人工智能领域优质创作者,华为云&middot;云享专家,CCF-TYUT President-designate
719
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载