AcWing 175 电路维修

题目传送门

一、算法分析

总结：就是一个\(Dijkstra\)的权值01版本,只不过\(Dijkstra\)用堆优化，这里可以用双端队列优化。
为了保持两段性和单调性，采用0入队头，1放队尾的方法进行队列维护。

双端队列

解决问题：
双端队列主要解决图中边的权值只有0或者1的最短路问题

操作：
每次从队头取出元素，并进行拓展其他元素时

• 若拓展某一元素的边权是0，则将该元素插入到队头
• 若拓展某一元素的边权是1，则将该元素插入到队尾

踩过格子到达想去的点时，需要判断是否需要旋转电线，若旋转电线表示从 当前点 到 想去的点 的边权是1，若不旋转电线则边权是0

二、代码实现

#include 

using namespace std;
const int INF = 0x3f3f3f3f;
#define x first
#define y second
typedef pair PII;
const int N = 510, M = N * N;
/**
[USACO08JAN]电话线Telephone Lines
CF1063B Labyrinth
CF1031D Minimum path
都可以在洛谷搜到
*/
int n, m;       // n行m列
char g[N][N];   //地图
int dist[N][N]; //距离出发点的最短步数
bool st[N][N];  //是不是走过(重复入队)
deque q;   //双端队列主要解决图中边的权值只有0或者1的最短路问题
int Min = INF;  //最小旋转数
void bfs() {
    //因为是多组数据，所以每次必须清空现场
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    Min = INF;
    //将{0,0}入队列，第一个要搜索的位置
    dist[0][0] = 0;
    q.push_back({0, 0});

    //左上，右上，右下，左下 四条斜线
    char cs[] = "\\/\\/";
    //根据上面四个方向，可以到达的点的delta值
    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};

    while (q.size()) {
        PII t = q.front();
        q.pop_front();

        if (st[t.x][t.y]) continue; //走过的不再走
        st[t.x][t.y] = true;

        for (int i = 0; i < 4; i++) {
            //可能走到的点
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 0 || a > n || b < 0 || b > m) continue;

            //走这个点，需要经过哪条边
            int ca = t.x + ix[i], cb = t.y + iy[i];

            //通过是否匹配计算权值是0，还是1，修改距离
            int d = dist[t.x][t.y] + (g[ca][cb] != cs[i]);
            //发现更小值
            if (d < dist[a][b]) {
                dist[a][b] = d; //更新更小值
                //权值为1，加到队列尾
                if (g[ca][cb] != cs[i])
                    q.push_back({a, b});
                else //权值为0，加到队列头
                    q.push_front({a, b});
            }
        }
    }
    Min = dist[n][m];
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> m;
        //输入地图,按cin读入是有换行符算一行，所以m没用上
        for (int i = 0; i < n; i++) cin >> g[i];

        bfs();
        if (Min == INF)
            puts("NO SOLUTION");
        else
            printf("%d\n", Min);
    }
    return 0;
}