題目分析

來源：acwing

只有邊權為0和邊權為1，兩種情況。什么意思呢？兩個點之間存在路徑則邊權為0，需要轉一下連通的邊權為1.

每個點可能入隊多次，本質上是個dijkstra算法。

下圖說明bfs枚舉周圍的4個點的坐標

我們還需要快速判斷每個方向上的邊是多少

ac代碼

#include<bits/stdc++.h> #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]; //有線路邊權為0，需要旋轉一下邊權為1，然后求最短路 bool st[N][N]; //某點是否更新完最短路int bfs(){memset(st, 0, sizeof st);memset(dist, 0x3f, sizeof dist);deque<PII> q;q.push_back({0, 0});dist[0][0] = 0;char cs[5] = "\\/\\/";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()){auto t = q.front();q.pop_front();int x = t.x, y = t.y;// 出隊列的時候，返回答案if( x == n && y == m) return dist[x][y];// 某點的最短路已算過，跳過if(st[x][y]) continue;st[x][y] = true;for(int i = 0; i < 4; i ++){// 擴展周圍的點int a = x + dx[i], b = y + dy[i];//判斷是否越界，這里合法點的坐標是x:[0,n],y:[0,m]都是閉區間if( a < 0 || a > n || b < 0 || b > m) continue;//方向在g數組中的坐標int ga = x + ix[i], gb = y + iy[i]; // 邊權：如果g數組中方向和要求的一致，則邊權為0，否則邊權為1int w = g[ga][gb] != cs[i];// 計算距離int d = dist[x][y] + (w);// 更新距離if(d < dist[a][b]){dist[a][b] = d;if(! w) q.push_front({a,b});else q.push_back({a,b});}}}return -1;}int main(){int T;cin >> T;while( T--){cin >> n >> m;for(int i = 0; i < n; i ++) cin >> g[i];if( n + m &1) cout << "NO SOLUTION"<<endl;else cout << bfs() << endl;} }

題目來源

https://www.acwing.com/problem/content/177/

總結

以上是生活随笔為你收集整理的算法提高课-搜索-双端队列广搜-AcWing 175. 电路维修：deque、bfs、有点难的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。