双端队列广搜———类dijkstra算法

题目链接

解决问题：

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

操作：

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

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

为什么两个移动dx和ix因为出发点和终点都是格点上坐标，但图的判断是方块坐标

#include<bits/stdc++.h>
using namespace std;
const int N=510;
typedef pair<int,int> PII;
#define x first
#define y second
int dist[N][N];
char g[N][N];
bool st[N][N];
int n,m;
int dx[4]={-1,-1,1,1},dy[4]={-1,1,-1,1};
int ix[4]={-1,-1,0,0},iy[4]={-1,0,-1,0};

int bfs()
{
    memset(st,0,sizeof st);
    memset(dist,0x3f,sizeof dist);
    deque<PII>q;
    dist[0][0]=0;
    q.push_back({0,0});
    char cs[]="\\//\\";
    while(q.size())
    {
        auto 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 aa=t.x+ix[i],bb=t.y+iy[i];
            int d=dist[t.x][t.y]+(g[aa][bb]!=cs[i]);
            if(d<dist[a][b])
            {
                dist[a][b]=d;
                if(g[aa][bb]!=cs[i])q.push_back({a,b});
                else q.push_front({a,b});
            }
        }
    }
    return dist[n][m];
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(int i=0;i<n;i++)cin>>g[i];
        int d=bfs();
        if(d==0x3f3f3f3f)cout<<"NO SOLUTION"<<endl;
        else cout<<d<<endl;
    }
}