詳解C++圖搜索算法之雙端隊列廣搜

第詳解C++圖搜索算法之雙端隊列廣搜目錄廣度優(yōu)先遍歷雙端隊列BFS例題：AcWing175.電路維修解題思路AC代碼

廣度優(yōu)先遍歷

廣度優(yōu)先遍歷是一種按照層次順序進行訪問的方法，它具有以下兩種重要性質(zhì)：

在訪問完所有第i層的結(jié)點后，才會去訪問第i+1層的結(jié)點任意時刻，隊列中至多有兩個層次的結(jié)點。若其中一部分結(jié)點屬于第i層，則另一部分結(jié)點屬于第i+1層，并且所有第i層結(jié)點排在第i+1層之前。也就是說，廣度優(yōu)先遍歷隊列中的元素關(guān)于層次滿足

雙端隊列BFS

在最基本的廣度優(yōu)先搜索中，每次沿著分支的擴展都記為一步，我們通過逐層搜索，解決了從起始狀態(tài)到每個狀態(tài)的最小步數(shù)的問題。這其實等價于在一張邊權(quán)均為1的圖上執(zhí)行廣度優(yōu)先遍歷，求出每個點相對于起點的最短距離（層次）。

由于廣度優(yōu)先遍歷具有兩段性和單調(diào)性，從而我們可以得知，每個狀態(tài)在第一次被訪問并且入隊時，計算出的步數(shù)即為所求的最短步數(shù)。

當(dāng)出現(xiàn)邊權(quán)不是0就是1的時候，可以考慮采用雙端隊列BFS的方法來進行求解。

基本思路：

如果拓展出來的點的邊權(quán)是0的話，就添加到隊頭如果拓展出來的點的邊權(quán)是1的話，就添加到隊尾

正確性:

在通過上述的方式添加元素后，隊列仍然能夠滿足兩段性和單調(diào)性，所以所求的結(jié)果即為最短路（層次）。

例題：AcWing175.電路維修

達達是來自異世界的魔女，她在漫無目的地四處漂流的時候，遇到了善良的少女翰翰，從而被收留在地球上。

翰翰的家里有一輛飛行車。

有一天飛行車的電路板突然出現(xiàn)了故障，導(dǎo)致無法啟動。

電路板的整體結(jié)構(gòu)是一個RR行CC列的網(wǎng)格（R,C500R,C500），如下圖所示。

每個格點都是電線的接點，每個格子都包含一個電子元件。

電子元件的主要部分是一個可旋轉(zhuǎn)的、連接一條對角線上的兩個接點的短電纜。

在旋轉(zhuǎn)之后，它就可以連接另一條對角線的兩個接點。

電路板左上角的接點接入直流電源，右下角的接點接入飛行車的發(fā)動裝置。

達達發(fā)現(xiàn)因為某些元件的方向不小心發(fā)生了改變，電路板可能處于斷路的狀態(tài)。

她準(zhǔn)備通過計算，旋轉(zhuǎn)最少數(shù)量的元件，使電源與發(fā)動裝置通過若干條短纜相連。

不過，電路的規(guī)模實在是太大了，達達并不擅長編程，希望你能夠幫她解決這個問題。

注意：只能走斜向的線段，水平和豎直線段不能走。

輸入格式

輸入文件包含多組測試數(shù)據(jù)。

第一行包含一個整數(shù)TT，表示測試數(shù)據(jù)的數(shù)目。

對于每組測試數(shù)據(jù)，第一行包含正整數(shù)RR和CC，表示電路板的行數(shù)和列數(shù)。

之后RR行，每行CC個字符，字符是/和\中的一個，表示標(biāo)準(zhǔn)件的方向。

輸出格式

對于每組測試數(shù)據(jù)，在單獨的一行輸出一個正整數(shù)，表示所需的最小旋轉(zhuǎn)次數(shù)。

如果無論怎樣都不能使得電源和發(fā)動機之間連通，輸出NOSOLUTION。

數(shù)據(jù)范圍

1R,C5001R,C500,

1T51T5

輸入樣例

1

\\/\\

\\///

/\\\\

輸出樣例

1

樣例解釋

樣例的輸入對應(yīng)于題目描述中的情況。

只需要按照下面的方式旋轉(zhuǎn)標(biāo)準(zhǔn)件，就可以使得電源和發(fā)動機之間連通。

解題思路

如圖所示，用紅圈所圈起來的點都是從起點出發(fā)所不能到達的（沿對角線行走的情況下）

從起點出發(fā)所能達到的點的坐標(biāo)之和應(yīng)為偶數(shù)，圖中所圈出來的點的坐標(biāo)之和均為奇數(shù)。

所以我們第一步可以使用這個性質(zhì)來判斷終點是否能夠到達。

然后使用雙端隊列來進行解答，在這道題目中對于格子和點的對應(yīng)關(guān)系需要進行思考。

將電路板上的每個格點（橫線和豎線的交叉點）看做是無向圖中的結(jié)點。如果對角線和x到y(tǒng)的線段重合，則邊權(quán)為0；若不重合，則邊權(quán)為1。

然后在圖中求出從左上角到右下角的最短距離。

踩過格子到達想去的點時，需要判斷是否需要旋轉(zhuǎn)電線。

若旋轉(zhuǎn)電線則表示從當(dāng)前點到想去的點的邊權(quán)是1，若不旋轉(zhuǎn)電線則邊權(quán)為0。

dx[]和dy[]表示可以去其他點的方向ix[]和iy[]表示需要踩某個方向的點才能去到相應(yīng)的點cs[]表示當(dāng)前點走到4個方向的點理想狀況下格子形狀（邊權(quán)是0的狀態(tài)）

AC代碼

#includeiostream

#includedeque

#includecstring

#includealgorithm

#definexfirst

#defineysecond

usingnamespacestd;

typedefpairint,intPII;

constintN=510;

intn,m;

charg[N][N];

intdist[N][N];;

dequePII

intbfs()

memset(dist,0x3f,sizeofdist);

q.push_front({0,0});

dist[0][0]=0;

intdx[]={-1,-1,1,1},dy[]={-1,1,1,-1};

intix[]={-1,-1,0,0},iy[]={-1,0,0,-1};

chars[]="\\/\\/";

while(q.size())

PIIt=q.front();

q.pop_front();

for(inti=0;ii++)

inta=t.x+dx[i],b=t.y+dy[i];

intaa=t.x+ix[i],bb=t.y+iy[i];

if(a0||an||b0||bm)continue;

intd=dist[t.x][t.y]+(g[aa][bb]!=s[i]);

if