01bfs

针对一类特殊图求最短路，如果边权只有01则可以使用双端队列代替堆，将最短路的时间复杂度从 \(O(nlogn)\) 降为 \(O(n)\) 。原理：每次所走边边权为0则放队首，边权为1则放队尾。

题目1

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define db double
#define il inline
#define x first
#define y second
#define endl '\n'
const int N=505;
const int mod=998244353;
char a[N][N];
int n,m;
int fx[4][2]={0,1,0,-1,1,0,-1,0};
int vis[N][N];
int safe(int x,int y) { return (x>=1)&&(x<=n)&&(y>=1)&&(y<=m); }
struct node { int x,y,w; };
void solve()
{
    while(cin>>n>>m&&n&&m)
    {
        memset(vis,0,sizeof vis);
        for(int i=1;i<=n;i++)
        {
            string p;cin>>p;
            for(int j=1;j<=m;j++) a[i][j]=p[j-1];
        }
        int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;
        deque<node>q;
        q.push_back({x1+1,y1+1,0});
        vis[x1+1][y1+1]=1;
        while(q.size())
        {
            auto [x,y,w]=q.front();
            q.pop_front();
            if(x==x2+1&&y==y2+1) 
            {
                cout<<w<<endl;
                break;
            }
            for(int i=0;i<4;i++)
            {
                int nx=x+fx[i][0],ny=y+fx[i][1];
                if(safe(nx,ny)&&vis[nx][ny]==0)
                {
                    vis[nx][ny]=1;
                    if(a[x][y]==a[nx][ny]) q.push_front({nx,ny,w});
                    else q.push_back({nx,ny,w+1});
                }
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T=1;//cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}

题目2

#include <bits/stdc++.h>
using namespace std;
//#define ll long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define db double
#define il inline
#define endl '\n'
const int N=2e3+5;
const int mod=998244353;
char a[N][N];
int n,m;
int fx[4][2]={0,1,0,-1,1,0,-1,0};
int vis[N][N];
int safe(int x,int y) { return (x>=1)&&(x<=n)&&(y>=1)&&(y<=m); }
struct node { int x,y,l,r; };
void solve()
{
    cin>>n>>m;
    int x,y;cin>>x>>y;
    int ll,rr;cin>>ll>>rr;
    for(int i=1;i<=n;i++)
    {
        string p;cin>>p;
        for(int j=1;j<=m;j++) a[i][j]=p[j-1];
    }
    deque<node>q;
    q.push_back({x,y,0,0});
    vis[x][y]=1;
    int ans=0;
    while(q.size())
    {
        auto [x,y,l,r]=q.front();
        q.pop_front();
        if(l<=ll&&r<=rr) ans++;
        for(int i=0;i<4;i++)
        {
            int nx=x+fx[i][0],ny=y+fx[i][1];
            if(vis[nx][ny]) continue;
            if(a[nx][ny]=='*') continue;
            if(!safe(nx,ny)) continue;
            vis[nx][ny]=1;
            if(fx[i][1]==-1) q.push_back({nx,ny,l+1,r});
            else if(fx[i][1]==1) q.push_back({nx,ny,l,r+1});
            else q.push_front({nx,ny,l,r});
        }
    }
    cout<<ans<<endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T=1;//cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}

题目3