Acwing 算法提高课 BFS(双端队列)

通过这条路如果需要转则操作数加1可以理解为走这条路的边权为1
所以本问题可以理解为边权只有1和0的最短路问题(基于特殊性质)，是标准的双端队列BFS问题
由于一条路只有两个点可能由起点走到所以不存在该路0和1冲突↑

Part1 双端队列正确性：
易知只要保证队列的单调性和两段性就能转化为dijkstra算法，即得证
而双端队列将边权为0的点放在队头，边权为1的放在队尾，即可保证这一性质


Part2 双端队列(deque) __ STL较为方便
qeque<type> object; __ define
object.push_front __ insert I
object.push_back __ insert II
pop 同理

Part3 双端队列一般算法框架：近似于dijkstra:
      I init 入起点
      II 取出队头并判断:(i  是否以及确定，若是则continue 否则令该点打上标记(已经确定)
                       (ii 是否到达终点，若是则return
      III 枚举上下左右各点并判断：
          (i  prepare 计算该点u并判断是否合法，计算w(边权), dist(距离)
         (ii tell 是否能更新，若是则尝试入队：
              边权为0则入队头
              边权为1则入队尾
      IIII 若到达此处(while外)则说明无最短路 return -1;(在本题中由于main中已经判断所以此句不会执行)

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <deque>
#define x first
#define y second

using namespace std;

const int N = 5e2 + 10;
typedef pair<int, int> PII;

int dx[4] = {-1, -1, 1, 1}, dy[4] = {-1, 1, -1, 1}, dgx[4] = {-1, -1, 0, 0}, dgy[4] = {-1, 0, -1, 0};
int check[4] = {1, 0, 0, 1};
int T, n, m, g[N][N], dist[N][N];
bool st[N][N];

int bfs(){
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    deque<PII> q;
    q.push_front({1, 1});
    dist[1][1] = 0;
    while(q.size()){
        int x = q.front().x, y = q.front().y;
        q.pop_front();
        
        if(x == n + 1 && y == m + 1)return dist[x][y];
        if(st[x][y])continue;
        st[x][y] = true;
        
        for(int i = 0; i < 4; i ++){
            int nx = x + dx[i], ny = y + dy[i], gx = x + dgx[i], gy = y + dgy[i];
            if(nx == 0 || nx > n + 1 || ny == 0 || ny > m + 1)continue;
            int w = (g[gx][gy] == check[i]);
            int d = dist[x][y] + w;
            if(d < dist[nx][ny]){
                dist[nx][ny] = d;
                if(!w)q.push_front({nx, ny});
                else q.push_back({nx, ny});
            }
        }
    }
    
    return -1;
}

int main(){
    scanf("%d", &T);
    while(T --){
       scanf("%d%d", &n, &m);
       for(int i = 1; i <= n; i ++){
           string s;
           cin >> s;
           
           for(int j = 1; j <= s.size(); j ++){
               if(s[j - 1] == '/') g[i][j] = 1;
               else g[i][j] = 0;
           }
       }
       
       if(n + m & 1)puts("NO SOLUTION");
       else{
           printf("%d\n", bfs());
       }
    }
    
    return 0;
}