廣度優(yōu)先遍歷

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

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

雙端隊(duì)列BFS

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

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

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

基本思路：

• 如果拓展出來(lái)的點(diǎn)的邊權(quán)是0的話，就添加到隊(duì)頭
• 如果拓展出來(lái)的點(diǎn)的邊權(quán)是1的話，就添加到隊(duì)尾

正確性:

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

例題：AcWing 175. 電路維修

達(dá)達(dá)是來(lái)自異世界的魔女，她在漫無(wú)目的地四處漂流的時(shí)候，遇到了善良的少女翰翰，從而被收留在地球上。

翰翰的家里有一輛飛行車(chē)。

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

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

每個(gè)格點(diǎn)都是電線的接點(diǎn)，每個(gè)格子都包含一個(gè)電子元件。

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

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

電路板左上角的接點(diǎn)接入直流電源，右下角的接點(diǎn)接入飛行車(chē)的發(fā)動(dòng)裝置。

達(dá)達(dá)發(fā)現(xiàn)因?yàn)槟承┰姆较虿恍⌒陌l(fā)生了改變，電路板可能處于斷路的狀態(tài)。

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

不過(guò)，電路的規(guī)模實(shí)在是太大了，達(dá)達(dá)并不擅長(zhǎng)編程，希望你能夠幫她解決這個(gè)問(wèn)題。

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

輸入格式

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

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

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

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

輸出格式

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

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

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

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

1≤T≤51≤T≤5

輸入樣例

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

輸出樣例

1

樣例解釋

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

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

解題思路

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

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

所以我們第一步可以使用這個(gè)性質(zhì)來(lái)判斷終點(diǎn)是否能夠到達(dá)。?

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

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

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

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

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

• dx[]和dy[]表示可以去其他點(diǎn)的方向
• ix[]和iy[]表示需要踩某個(gè)方向的點(diǎn)才能去到相應(yīng)的點(diǎn)
• cs[]表示當(dāng)前點(diǎn)走到4個(gè)方向的點(diǎn)理想狀況下格子形狀（邊權(quán)是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;
}

每個(gè)結(jié)點(diǎn)雖然可能被更新（入隊(duì)）多次，但是它第一次被拓展（出隊(duì)）時(shí)，就能得到從左上角到該點(diǎn)的最短距離，之后再取出可以直接忽略。

時(shí)間復(fù)雜度是O(M * N)