文章目录
前言
一、双端队列广搜
二、AcWing 175. 电路维修
本题解析：
AC代码
三、时间复杂度
前言
复习acwing算法提高课的内容，本篇为讲解算法：双端队列广搜，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。
一、双端队列广搜
双端队列主要是解决边权只有 0 和 1 的这类问题，我们把边权为 0 的边加入到对头，把边权为 1 的边加入到队尾，同堆优化版的 Dijkstra 一样，只有在出队的时候才能知道最小值
二、AcWing 175. 电路维修
本题链接：AcWing 175. 电路维修
本博客提供本题截图：
本题解析：
因为是四个方向上的扩展，所以我们使用向量的形式进行对边的扩展，这里注意有的点我们是肯定到达不了的，因为我们每次移动的时候，横坐标和纵坐标总是在同时变化的，且我们的初始点为(0, 0)，所以我们只能到达横纵坐标之和为偶数的点，横纵坐标之和为奇数的点我们无论如何都是到达不了的，数组dx,dy存储的是四个方向点的变化，ix，iy存储的是表示需要踩某个方向的各种才能去到相应的点，如图所示：
dx，dy表示的就红色的点之间的变化过程，ix，iy表示的就是红色的点走到绿色的边的坐标变化过程
cs数组表示的就是表示当前点（正中间的红色的点）走到4个方向的点理想状态（图中其他红色四个点）下格子形状（图中绿色线条）(边权是0的状态)，注意cs中表示反斜杠这种边需要写成\\
时间复杂度 O(nm)
AC代码
#include <cstring> #include <iostream> #include <algorithm> #include <deque> #define x first #define y second using namespace std; typedef pair<int, int> PII; const int N = 510, M = N * N; int n, m; char g[N][N]; int dist[N][N]; bool st[N][N]; int bfs() { memset(dist, 0x3f, sizeof dist); memset(st, 0, sizeof st); dist[0][0] = 0; deque<PII> q; q.push_back({0, 0}); char cs[] = "\\/\\/"; int dx[4] = {-1, -1, 1, 1}, dy[4] = {-1, 1, 1, -1}; int ix[4] = {-1, -1, 0, 0}, iy[4] = {-1, 0, 0, -1}; while (q.size()) { PII t = q.front(); q.pop_front(); if (st[t.x][t.y]) continue; st[t.x][t.y] = true; 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 > m) continue; int ca = t.x + ix[i], cb = t.y + iy[i]; int d = dist[t.x][t.y] + (g[ca][cb] != cs[i]); if (d < dist[a][b]) { dist[a][b] = d; if (g[ca][cb] != cs[i]) q.push_back({a, b}); //即需要旋转，边权为1，放入队尾 else q.push_front({a, b}); //即不需要旋转，边权为0，放在队头 } } } return dist[n][m]; } int main() { int T; scanf("%d", &T); while (T -- ) { scanf("%d%d", &n, &m); for (int i = 0; i < n; i ++ ) scanf("%s", g[i]); if (n + m & 1) puts("NO SOLUTION"); else printf("%d\n", bfs()); } return 0; }
三、时间复杂度
关于双端队列广搜的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
