對于權重為0或1的路徑搜索中，使用雙端隊列可以對最短路問題進行時間復雜度的優化，由于優先隊列的O(longn)級別的插入時間，對于雙端隊列O(1)插入可以將時間復雜度減少至O(M);

https://www.luogu.com.cn/problem/P4667

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
bool tin=0;
char ma[505][505];// 存圖 
int vis[505][505],se[505][505];//vis記錄步數，se記錄是否出過一次隊列 
deque <array<int,2>> dq;//雙端隊列記錄點 
int dx[]={-1,-1,1,1},dy[]={-1,1,1,-1},ex[]={-1,-1,0,0},ey[]={-1,0,0,-1};
//dx，dy為下一個點的位移量，ex，ey為對應格子的位移 
string s="\\/\\/";//正確連接的狀態，符合該狀態即無需旋轉 
void solve()
{int n,m;cin>>n>>m;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>ma[i][j];//輸入圖 }}for(int i=0;i<=n;i++){for(int j=0;j<=m;j++){vis[i][j]=INT_MAX;se[i][j]=0;//重置位置以及步數數組 }}dq.push_back({0,0});vis[0][0]=0;//存入起點 while(!dq.empty()){int x=dq.front()[0],y=dq.front()[1];dq.pop_front();//取頭點 if(se[x][y])continue;se[x][y]=1;//來過不再進行 for(int i=0;i<4;i++){int xx=x+dx[i],yy=y+dy[i],exx=x+ex[i],eyy=y+ey[i];//算出下一個點以及兩點間對應的連接情況 if(xx<0||xx>n||yy<0||yy>m)	continue;//越界 int d=vis[x][y]+(ma[exx][eyy]!=s[i]);//距離 if(d<vis[xx][yy])//更優距離就更新 {vis[xx][yy]=d;if(ma[exx][eyy]==s[i]){dq.push_front({xx,yy});//是正確連接放在頭部 }elsedq.push_back({xx,yy});//否則放在尾部 }}	}if(vis[n][m]==INT_MAX)cout<<"NO SOLUTION";elsecout<<vis[n][m];
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);int T=1;if(tin)cin>>T;while(T--){solve();}return 0;
}