題目鏈接

電路維修

題目描述

達達是來自異世界的魔女，她在漫無目的地四處漂流的時候，遇到了善良的少女翰翰，從而被收留在地球上。翰翰的家里有一輛飛行車。有一天飛行車的電路板突然出現了故障，導致無法啟動。

電路板的整體結構是一個$R$行$C$列的網格（$R,C\le 500$），如下圖所示：

每個格點都是電線的接點，每個格子都包含一個電子元件。電子元件的主要部分是一個可旋轉的、連接一條對角線上的兩個接點的短電纜。在旋轉之后，它就可以連接另一條對角線的兩個接點。電路板左上角的接點接入直流電源，右下角的接點接入飛行車的發動裝置。

達達發現因為某些元件的方向不小心發生了改變，電路板可能處于斷路的狀態。她準備通過計算，旋轉最少數量的元件，使電源與發動裝置通過若干條短纜相連。不過，電路的規模實在是太大了，達達并不擅長編程，希望你能夠幫她解決這個問題。

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

輸入描述

輸入文件包含多組測試數據。

第一行包含一個整數$T$，表示測試數據的數目。對于每組測試數據，第一行包含正整數$R$和$C$，表示電路板的行數和列數。

之后$R$行，每行$C$個字符，字符是/和\中的一個，表示標準件的方向。

輸出描述

對于每組測試數據，在單獨的一行輸出一個正整數，表示所需的縮小旋轉次數。
如果無論怎樣都不能使得電源和發動機之間連通，輸出NO SOLUTION。

樣例輸入

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

樣例輸出

1

算法思想

根據題目描述，每個格子都包含一個電子元件，主要部分是一個可旋轉的、連接一條對角線上的兩個接點的短電纜，如下圖所示。

旋轉一個電子元件的代價為$1$，問最少旋轉幾個元件，使起點與終點通過若干條短纜相連。

連通性

由于只能走斜向的線段，水平和豎直線段不能走，所以選擇左上角的接點作為起點，只能連接如下圖（左）綠色的接點，二下圖（右）紅色的接點是無法連通的。

通過分析發現，如果將起點設為左上角，那么能夠連接的點（綠色），其行列值的和為偶數。因此，是否使得電源和發動機之間連通，需要判斷$(n+m)$是否為偶數。

最小代價

如果電子元件的最初狀態為下圖所示，那么從$A?>B$的代價為$0$，不需要旋轉；而從$C?>D$的代價為$1$，需要旋轉$1$次。

因此，求旋轉最少數量的元件，使電源與發動裝置通過若干條短纜相連，可以轉換為求從起點到終點，當連接的兩點之間代價為$0$或$1$時的最短路。

雙端隊列廣搜

對于只包含邊權$0$和$1$的最短路問題，可以使用雙端隊列廣搜求解。與普通的BFS不同的是：

• 如果擴展到的新節點邊權為$0$時，需要把新節點插入隊列的頭部。

這樣處理滿足BFS的兩個性質：

• 兩段性：隊列中同時存在的所有點到起點的距離差值最多是1。
• 單調性：隊列分成兩段，前面一定是小的

因此可以使用BFS求最短路。

代碼實現

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;typedef pair<int, int> PII;
const int N = 505;
char g[N][N];
int n, m, st[N][N], dis[N][N];//元件的偏移值:左上，右上，右下，左下
int dx[4] = {-1, -1, 1, 1}, dy[4] = {-1, 1, 1, -1};
//連接元件的電纜方向在字符數組位置的偏移值:左上，右上，右下，左下
int ix[4] = {-1, -1, 0, 0}, iy[4] = {-1, 0, 0, -1};
//不需要旋轉的連接方向，左上，右上，右下，左下
char c[] = "\\/\\/"; //"\/\/"
int bfs()
{memset(st, 0, sizeof st);memset(dis, 0x3f, sizeof dis);deque<PII> q;dis[0][0] = 0; q.push_back({0, 0});while(q.size()){PII t = q.front(); q.pop_front(); //從隊頭出隊int x = t.first, y = t.second;if(st[x][y]) continue;st[x][y] = true;for(int i = 0; i < 4; i ++){//擴展到的元件左上角的行列值int a = x + dx[i], b = y + dy[i]; if(a < 0 || a > n || b < 0 || b > m) continue;int ai = x + ix[i], bi = y + iy[i];//元件方向在數組中的位置int w = g[ai][bi] != c[i]; //如果不是正確的連接方向，需要旋轉，邊權為1if(dis[a][b] > dis[x][y] + w){dis[a][b] = dis[x][y] + w;if(w == 1) q.push_back({a, b}); //邊權為1加入隊尾else q.push_front({a, b}); //邊權為0加入隊頭}}}return dis[n][m];
}
int main()
{int T;cin >> T;while(T --){cin >> n >> m;for(int i = 0; i < n; i ++) cin >> g[i];if(n + m & 1) {puts("NO SOLUTION");continue;}int t = bfs();if(t == 0x3f3f3f3f) puts("NO SOLUTION");else cout << t << '\n';}
}