電路維修（搜尋、雙端隊列BFS）————《算法競賽進階指南》

電路維修

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

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

有一天飛行車的電路闆突然出現了故障，導緻無法啟動。

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

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

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

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

電路闆左上角的接點接入直流電源，右下角的接點接入飛行車的發動裝置。

達達發現因為某些元件的方向不小心發生了改變，電路闆可能處于斷路的狀态。

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

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

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

輸入格式

輸入檔案包含多組測試資料。

第一行包含一個整數 T，表示測試資料的數目。

對于每組測試資料，第一行包含正整數 R 和 C，表示電路闆的行數和列數。

之後 R 行，每行 C 個字元，字元是"/“和”"中的一個，表示标準件的方向。

輸出格式

對于每組測試資料，在單獨的一行輸出一個正整數，表示所需的最小旋轉次數。

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

資料範圍

1≤R,C≤500,

1≤T≤5

輸入樣例：

1

3 5

\/\

\///

/\\

輸出樣例：

1

題解

前置知識：迪傑特斯拉算法：每次拿出一個距離起點最短的點并且這個點之前沒有被拿出過，用這個點來更新到所有點的距離，直到所有點都拿出過一次，停止，此時就求得了每個點的單源最短路

此題使用雙端隊列實作迪傑特斯拉算法可求得最短的路線

分析：

雙端隊列主要解決圖中邊的權值隻有0或者1的最短路問題

假設：題中如果需要旋轉電纜，那麼設這個邊的邊權為1，如果不需要旋轉，則這個邊邊權為0。

題目就轉化為 ——> 圖中邊的權值隻有0或者1的最短路問題

每次的操作：每次從隊頭取出一個元素，拓展此點到其他點：

• 如果邊權為 0 ，加入隊頭
• 如果邊權為1，加入隊尾

  

  圖檔來源于 https://www.acwing.com/solution/content/21775/

下面代碼中

• n e x t d [ 4 ] [ 2 ] nextd[4][2] nextd[4][2]數組表示從一個點去往其他點的關系 (圖中的dx[]和dy[])
• n e x t i [ 4 ] [ 2 ] nexti[4][2] nexti[4][2]數組表示從一個點去往其他點需要踩過的格子的位置 之間的關系 (圖中的ix[]和iy[])
• c s [ ] cs[] cs[]表示目前點走到4個方向的點理想狀态下格子形狀(邊權是0的狀态)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second

const int N = 505,M=N*N;
int n,m;
char g[N][N];
int dist[N][N];
bool st[N][N];
int bfs()
{
    memset(st, 0, sizeof st);
    memset(dist,0x3f,sizeof dist);
    dist[0][0]=0;
    deque<PII> q;
    q.push_back({0,0});
    char cs[] = "\\/\\/";
    int nextd[4][2]={{-1,-1},{-1,1},{1,1},{1,-1}};
    int nexti[4][2]={{-1,-1},{-1,0},{0,0},{0,-1}};
    while(q.size()){
        PII t = q.front();
        q.pop_front();
        if(st[t.x][t.y]) continue;
        st[t.x][t.y]=true;
        
        for(int i=0; i<4; ++i){
            int a = t.x + nextd[i][0], b = t.y + nextd[i][1];
            if(a<0 || a>n || b<0 || b>m) continue;
            int ca = t.x + nexti[i][0], cb = t.y + nexti[i][1];
            int d = dist[t.x][t.y] + (g[ca][cb]!=cs[i]);
            
            if(d < dist[a][b]){
                dist[a][b] = d;
                
                if(g[ca][cb]!=cs[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]);
        int t = bfs();
        if(t == 0x3f3f3f3f) puts("NO SOLUTION");
        else printf("%d\n",t);
    }
    return 0;
}