双端队列广搜 AcWing 175. 电路维修

素颜马尾好姑娘i 2024-04-08 13:43 13阅读 0赞

## 双端队列广搜 AcWing 175. 电路维修 ##

### 原题链接 ###

[双端队列广搜 AcWing 175. 电路维修][AcWing 175.]

### 算法标签 ###

搜索 双端队列BFS

### 思路 ###

对于图中边的权值只有0或者1的最短路问题， 采用双端队列解决

#### 操作 ####

![在这里插入图片描述][cd9aebc3420e4fe694a992629f471096.png]  
![请添加图片描述][3ef01f49a3d34d088540828b8cea5de9.png]  
踩格子到达下个点时，需要判断是否需要旋转电线，若旋转电线表示从 当前点 到 想去的点 的边权是1，若不旋转电线则边权是0

#include<bits/stdc++.h>
    #define int long long
    #define rep(i, a, b) for(int i=a;i<b;++i)
    #define Rep(i, a, b) for(int i=a;i>b;--i)
    #define x first
    #define y second
    using namespace std;
    typedef pair<int, int> PII;
    const int N=1005, INF=0x3f3f3f3f;
    int n, m;
    char g[N][N];
    bool st[N][N];
    int d[N][N];
    inline int read(){
       int s=0,w=1;
       char ch=getchar();
       while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
       while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
       return s*w;
    }
    int bfs(){
        memset(d, 0x3f, sizeof d);
        memset(st, false, sizeof st);
        d[0][0]=0;
        deque<PII> q;
        q.push_back({0, 0});
        // dx存储方向 依次左上 右上 右下 左下  
        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};
        // 表示当前点到达4个方向的点理想状态下格子形状(边权是0的状态
        char c[]="\\/\\/";
        while(q.size()){
            PII t=q.front();
            q.pop_front();
            if(st[t.x][t.y]){
                continue;
            }
            st[t.x][t.y]=true;
            rep(i, 0, 4){
                int x=t.x+dx[i], y=t.y+dy[i];
                if(x<0||x>n||y<0||y>m){
                    continue;
                }
                int cx=t.x+ix[i], cy=t.y+iy[i];
                // 增加边权 字符与对应方向是否一致 不一致增加边权 
                int dd=d[t.x][t.y]+(g[cx][cy]!=c[i]);
                if(dd<d[x][y]){
                    d[x][y]=dd;
                    // 若字符与对应方向不一致 将该点插入队尾 
                    if(g[cx][cy]!=c[i]){
                        q.push_back({x, y});
                    }else{// 若字符与对应方向一致 将该点插入队头 
                        q.push_front({x, y});
                    }
                }
            }
        }
        return d[n][m];
    }
    void put(int x) {
        if(x<0) putchar('-'),x=-x;
        if(x>=10) put(x/10);
        putchar(x%10^48);
    }
    signed main(){
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
    	int t=read();
    	while(t--){
    	    n=read(), m=read();
    	    rep(i, 0, n){
    	        scanf("%s",g[i]);
    	    }
    	    int ans=bfs();
    	    if(ans>=INF){
    	        puts("NO SOLUTION");
    	    }else{
    	        printf("%lld\n", ans);
    	    }
    	}
    	return 0;
    }

参考文献  
[AcWing 175. 电路维修题解][AcWing 175. 1]  
[AcWing 175. 电路维修y总代码][AcWing 175. _y]

原创不易  
转载请标明出处  
如果对你有所帮助 别忘啦点赞支持哈  
![在这里插入图片描述][9cb4cb80a18345158f8a69e2f196e5b9.png]

[AcWing 175.]: https://www.acwing.com/problem/content/177/
[cd9aebc3420e4fe694a992629f471096.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/e56cae0bf0f84641a721f26dfde58ce6.png
[3ef01f49a3d34d088540828b8cea5de9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/e07c83204d474130870c7db2c41e0fcf.png
[AcWing 175. 1]: https://www.acwing.com/solution/content/21775/
[AcWing 175. _y]: https://www.acwing.com/activity/content/code/content/132139/
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/ac8c3df3cb094950a1ec36e65b1a6945.png