【广搜】电路维修

我不是女神ヾ 2021-10-29 13:22 364阅读 0赞

#### 题目描述 ####

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

![20180620220555_20581.png][]

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

#### 输入 ####

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

#### 输出 ####

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

## 样例输入 ##

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

#### 样例输出 ####

#### 提示 ####

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

【思路】

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

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

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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 }

电路维修

转载于:https://www.cnblogs.com/Osea/p/11214534.html

[20180620220555_20581.png]: /images/20211029/3e53a094307941b0870e097a171b4a13.png
[20180620220628_83898.png]: /images/20211029/2759d570cf214c40af53bf62ca6e9443.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211029/f1cea16fb67d4284a7dfbd902c12a758.png