詳解C++圖搜尋演演算法之雙端佇列廣搜

2022-06-14 14:00:20

廣度優先遍歷

廣度優先遍歷是一種按照層次順序進行存取的方法，它具有以下兩種重要性質：

在存取完所有第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++雙端佇列廣搜的資料請關注it145.com其它相關文章！