题解：B4584 [合肥市小学组 2026 T4] 信号接力

xiaomi1026 · 2026-11-10 12:42:22 · 题解

思路

显然，最优方案就是将最短路外所有工作的中继器关闭。也就是说本题答案就是最短路外所有工作的中继器的数量。
由于此题信号网只有 2 行，所以没必要用到 bfs 算法。考虑一下简单写法：如果右边可以通过，就走右边；不然，则换到另外一行。并注意一下边界处理即可。

代码

#include<bits/stdc++.h>
using namespace std;
char c[3][2010];
int main(){
    long long n,cnt=0;
    cin>>n;
    for(int i=1;i<=2;i++){
        for(int j=1;j<=n;j++){
            cin>>c[i][j];
            if(c[i][j]=='#') cnt++;
        }
    }
    c[1][n+1]='#';//边界处理。
    long long dx=1,dy=1,Cnt=0;
    while(dx!=2||dy!=n){
        Cnt++;
        if(c[dx][dy+1]=='.') dy++;
        else{
            if(dx==2) dx=1;
            else dx=2;
        }
    }
    Cnt++;//注意最短路要记入终点。
    cout<<2*n-Cnt-cnt;
    return 0;
}