算法提高之电路维修

• 核心思想：双端队列bfs

  • dijkstra算法的拓展情况：边权(旋转次数)只有0和1

  • dijkstra算法要求：每次取离原点最近的点 去更新其他相邻点距离(多次)

    • 如何实现：将所有边权为0的边连的点放入队头，边权为1的放入队尾

    • 

    • 此时队头一定是距离原点最近的点(之一)

•   #include <iostream>
    #include <cstring>
    #include <algorithm>
    #include <deque>
    
    #define x first
    #define y second
    
    using namespace std;
    typedef pair<int, int> PII;
    
    const int N = 510,M = N*N;
    int dist[N][N];
    int n,m;
    char g[N][N];  //存图
    bool st[N][N];
    char cs[] = "\\/\\/";  //顺时针四个方向的图案
    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};  //四个格方向
    
    int bfs()
    {
        deque<PII> q;
        q.push_back({0,0});
        memset(st, 0, sizeof st);  //多组数据 清空
        memset(dist,0x3f,sizeof dist);
        dist[0][0] = 0;
        
        while(q.size())
        {
            PII t = q.front();
            q.pop_front();
            
            int x = t.x,y = t.y;
            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 ga = x+ix[i],gb = y+iy[i];  //格子坐标
                int w = (g[ga][gb] != cs[i]);  //边权：当前图案和合法图案不一致 为需要旋转的1
                int d = dist[x][y] + w;  //新的距离
                if(d < dist[a][b])
                {
                    dist[a][b] = d;
                    if(w) q.push_back({a,b});  //边权为1 加到队尾
                    else q.push_front({a,b});
                }
            }
        }
        return dist[n][m];  //点(n,m)到原点距离
    }
    int main()
    {
        int T;
        cin>>T;
        while(T--)
        {
            cin>>n>>m;
            for(int i=0;i<n;i++) cin>>g[i];
            
            int t = bfs();
            if(t == 0x3f3f3f3f) puts("NO SOLUTION");
            else cout<<t<<endl;
        }
    }