【广搜】电路维修-蒲公英云

【广搜】电路维修

题目描述

Ha’nyu是来自异世界的魔女，她在漫无目的地四处漂流的时候，遇到了善良的少女Rika，从而被收留在地球上。Rika的家里有一辆飞行车。有一天飞行车的电路板突然出现了故障，导致无法启动。
电路板的整体结构是一个R行C列的网格（R,C≤500），如右图所示。每个格点都是电线的接点，每个格子都包含一个电子元件。电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。在旋转之后，它就可以连接另一条对角线的两个接点。电路板左上角的接点接入直流电源，右下角的接点接入飞行车的发动装置。

Ha’nyu发现因为某些元件的方向不小心发生了改变，电路板可能处于断路的状态。她准备通过计算，旋转最少数量的元件，使电源与发动装置通过若干条短缆相连。不过，电路的规模实在是太大了，Ha’nyu并不擅长编程，希望你能够帮她解决这个问题。

输入

输入包含多组测试数据。第一行包含一个整数T 表示测试数据的数目。
对于每组测试数据，第一行包含正整数R 和C，表示电路板的行数和列数。
之后R 行，每行C 个字符，字符是”/“和”\“中的一个，表示标准件的方向。

输出

对于每组测试数据，在单独的一行输出一个正整数，表示所需的缩小旋转次数。
如果无论怎样都不能使得电源和发动机之间连通，输出NO SOLUTION。

样例输入

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

样例输出

提示

对于40% 的数据，R,C≤5。
对于100% 的数据，R,C≤500，T≤5。
样例解释
样例的输入对应于题目描述中的情况。
只需要按照下面的方式旋转标准件，就可以使得电源和发动机之间连通。

【思路】

　　这个是一个边权为要么1，要么0的无向图，在这样的图上，我们可以通过双端队列广搜搜索来计算。算法的整体框架与一般的广搜类似，只是在每个结点上沿分支扩展时稍作改变。如果这条分支是边权为0的边，就把沿该分支到达的新结点从队头入队；如果这条分支是边权为1的边，就像一般的广搜搜索一样从队尾入队，这样一来，我们就仍能保证任意时刻广搜搜索队列中的结点对应的距离都具有”两段性“和”单调性“，每个结点从队头出队时，就能得到从左上角到该节点的最短距离。

　　因为每个节点只需要访问一次，所以算法的时间复杂度为O(R*C)

1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N = 505;
 4 int dis[N][N];
 5 char s[N][N];
 6 int n,m;
 7 typedef struct Node {
 8     int x,y;
 9 }Node;
10 deque <Node> Q ;
11 void Push ( int x,int y,int s,int k ){
12     if( s+k < dis[x][y] ){
13         dis[x][y] = s+k ;
14         if(!k)    Q.push_front ( Node{x,y} );
15         else     Q.push_back ( Node{x,y} ) ;
16     }
17 }
18 int dir[4][2] = {
19     {-1,-1} , {-1,1},
20     {
      1,-1}, {
      1,1}
21 };
22 char Str[] = {
      "\\//\\"};
23 void BFS(){
24     memset(dis,0x7f,sizeof dis);
25     Q.push_front ( Node{
      1,1} ) ;
26     dis[1][1] = 0 ;
27     while ( !Q.empty() ){
28         Node cur = Q.front();
29         Q.pop_front();
30         int x = cur.x , y = cur.y ;
31         for(int i=0;i<4;i++){
32             int tx = x + dir[i][0] ;
33             int ty = y + dir[i][1] ;
34             int dx = x + (dir[i][0] == 1 ? 0:-1) ;
35             int dy = y + (dir[i][1] == 1 ? 0:-1) ;
36             if( 1 <= tx && tx <= n+1 && 1 <= ty && ty <= m+1 ){
37                 Push(tx,ty,dis[x][y], ( Str[i] != s[dx][dy] ));
38             }
39         }
40     }
41     printf("%d\n",dis[n+1][m+1]);
42 }
43 int main()
44 {
45     int T;
46     for(scanf("%d",&T);T;T--){
47         scanf("%d%d",&n,&m);
48         for(int i=1;i<=n;i++){
49             scanf("%s",s[i]+1 );
50         }
51         if( (n+m)&1 ){
52             printf("NO SOLUTION\n");
53         }else{
54             BFS();
55         }
56     }
57     return 0;
58 }