廣度優(yōu)先遍歷

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

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

雙端隊列BFS

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

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

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

基本思路：

• 如果拓展出來的點的邊權是0的話，就添加到隊頭
• 如果拓展出來的點的邊權是1的話，就添加到隊尾

正確性:

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

例題：AcWing 175. 電路維修

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

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

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

電路板的整體結構是一個 RR 行 CC 列的網格（R,C≤500R,C≤500），如下圖所示。

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

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

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

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

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

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

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

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

輸入格式

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

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

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

之后 RR 行，每行 CC 個字符，字符是"/"和"\"中的一個，表示標準件的方向。

輸出格式

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

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

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

1≤R,C≤5001≤R,C≤500,

1≤T≤51≤T≤5

輸入樣例

1
3 5
\\/\\
\\///
/\\\\

輸出樣例

1

樣例解釋

樣例的輸入對應于題目描述中的情況。

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

解題思路

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

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

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

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

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

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

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

若旋轉電線則表示從當前點到想去的點的邊權是1，若不旋轉電線則邊權為0。

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

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)