詳解C++圖搜索算法之雙端隊列廣搜
廣度優先遍歷
廣度優先遍歷是一種按照層次順序進行訪問的方法，它具有以下兩種重要性質：
- 在訪問完所有第i層的結點後，才會去訪問第i+1層的結點
- 任意時刻，隊列中至多有兩個層次的結點。若其中一部分結點屬於第i層，則另一部分結點屬於第i+1層，並且所有第i層結點排在第i+1層之前。也就是說，廣度優先遍歷隊列中的元素關於層次滿足
雙端隊列BFS
在最基本的廣度優先搜索中，每次沿著分支的擴展都記為“一步”，我們通過逐層搜索，解決瞭從起始狀態到每個狀態的最小步數的問題。這其實等價於在一張邊權均為1的圖上執行廣度優先遍歷，求出每個點相對於起點的最短距離（層次）。
由於廣度優先遍歷具有“兩段性”和“單調性”，從而我們可以得知，每個狀態在第一次被訪問並且入隊時，計算出的步數即為所求的最短步數。
當出現邊權不是0就是1的時候，可以考慮采用雙端隊列BFS的方法來進行求解。
基本思路：
- 如果拓展出來的點的邊權是0的話，就添加到隊頭
- 如果拓展出來的點的邊權是1的話，就添加到隊尾
正確性:
在通過上述的方式添加元素後，隊列仍然能夠滿足“兩段性”和“單調性”，所以所求的結果即為最短路（層次）。
例題：AcWing 175. 電路維修
達達是來自異世界的魔女，她在漫無目的地四處漂流的時候，遇到瞭善良的少女翰翰，從而被收留在地球上。
翰翰的傢裡有一輛飛行車。
有一天飛行車的電路板突然出現瞭故障，導致無法啟動。
電路板的整體結構是一個 RR 行 CC 列的網格（R,C≤500R,C≤500），如下圖所示。
每個格點都是電線的接點，每個格子都包含一個電子元件。
電子元件的主要部分是一個可旋轉的、連接一條對角線上的兩個接點的短電纜。
在旋轉之後，它就可以連接另一條對角線的兩個接點。
電路板左上角的接點接入直流電源，右下角的接點接入飛行車的發動裝置。
達達發現因為某些元件的方向不小心發生瞭改變，電路板可能處於斷路的狀態。
她準備通過計算，旋轉最少數量的元件，使電源與發動裝置通過若幹條短纜相連。
不過，電路的規模實在是太大瞭，達達並不擅長編程，希望你能夠幫她解決這個問題。
註意：隻能走斜向的線段，水平和豎直線段不能走。
輸入格式
輸入文件包含多組測試數據。
第一行包含一個整數 TT，表示測試數據的數目。
對於每組測試數據，第一行包含正整數 RR 和 CC，表示電路板的行數和列數。
之後 RR 行，每行 CC 個字符，字符是"/"和"\"中的一個，表示標準件的方向。
輸出格式
對於每組測試數據，在單獨的一行輸出一個正整數，表示所需的最小旋轉次數。
如果無論怎樣都不能使得電源和發動機之間連通，輸出 NO SOLUTION。
數據范圍
1≤R,C≤5001≤R,C≤500,
1≤T≤51≤T≤5
輸入樣例
1 3 5 \\/\\ \\/// /\\\\
輸出樣例
1
樣例解釋
樣例的輸入對應於題目描述中的情況。
隻需要按照下面的方式旋轉標準件，就可以使得電源和發動機之間連通。
解題思路
如圖所示，用紅圈所圈起來的點都是從起點出發所不能到達的（沿對角線行走的情況下）
從起點出發所能達到的點的坐標之和應為偶數，圖中所圈出來的點的坐標之和均為奇數。
所以我們第一步可以使用這個性質來判斷終點是否能夠到達。
然後使用雙端隊列來進行解答，在這道題目中對於格子和點的對應關系需要進行思考。
將電路板上的每個格點（橫線和豎線的交叉點）看做是無向圖中的結點。如果對角線和x到y的線段重合，則邊權為0；若不重合，則邊權為1。
然後在圖中求出從左上角到右下角的最短距離。
踩過格子到達想去的點時，需要判斷是否需要旋轉電線。
若旋轉電線則表示從當前點到想去的點的邊權是1，若不旋轉電線則邊權為0。
- dx[]和dy[]表示可以去其他點的方向
- ix[]和iy[]表示需要踩某個方向的點才能去到相應的點
- cs[]表示當前點走到4個方向的點理想狀況下格子形狀（邊權是0的狀態）
AC代碼
#include<iostream>
#include<deque>
#include<cstring>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 510;
int n,m;
char g[N][N];
int dist[N][N];;
deque<PII> q;
int bfs()
{
memset(dist,0x3f,sizeof dist);
q.push_front({0,0});
dist[0][0]=0;
int dx[]={-1,-1,1,1},dy[]={-1,1,1,-1};
int ix[]={-1,-1,0,0},iy[]={-1,0,0,-1};
char s[]="\\/\\/";
while(q.size())
{
PII t=q.front();
q.pop_front();
for(int i=0;i<4;i++)
{
int a=t.x+dx[i],b=t.y+dy[i];
int aa=t.x+ix[i],bb=t.y+iy[i];
if(a<0||a>n||b<0||b>m) continue;
int d = dist[t.x][t.y]+(g[aa][bb]!=s[i]);
if (d < dist[a][b])
{
dist[a][b] = d;
if (g[aa][bb] != s[i]) q.push_back({a, b});
else q.push_front({a, b});
}
}
}
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)%2==1)
{
puts("NO SOLUTION");
continue;
}
cout<<bfs()<<endl;
}
return 0;
}
每個結點雖然可能被更新（入隊）多次，但是它第一次被拓展（出隊）時，就能得到從左上角到該點的最短距離，之後再取出可以直接忽略。
時間復雜度是O(M * N)
以上就是詳解C++圖搜索算法之雙端隊列廣搜的詳細內容，更多關於C++雙端隊列廣搜的資料請關註WalkonNet其它相關文章！