文章目录
前言
一、最短路
二、例题，代码
AcWing 1076. 迷宫问题
本题分析
AC代码
AcWing 188. 武士风度的牛
本题分析
AC代码
AcWing 1100. 抓住那头牛
本题分析
AC代码
三、时间复杂度
前言
复习acwing算法提高课的内容，本篇为讲解算法：最短路模型，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。
一、最短路
我们在算法基础部分已经说明了几种计算最短路的方式：Dijkstra，bellman-ford，spfa，Floyd，我们也可以通过bfs去计算最短路（边权一样），在这里的最短路模型中我们用到的核心思想就是bfs中的思想
二、例题，代码
AcWing 1076. 迷宫问题
本题链接：AcWing 1076. 迷宫问题
本博客提供本题截图：
本题分析
核心思路是不会变的，都是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; }
