双端队列广搜

分层图 01/BFS
https://ac.nowcoder.com/acm/contest/45670/D
#include<bits/stdc++.h>
using namespace std;

const int N = 2009;
int n,m,k;
int sx,sy,ex,ey;
int a[N][N];
int dist[N][N][2];
const int dx[] = {1,-1,0,0},dy[] = {0,0,1,-1};
void bfs() {
    memset(dist,0x3f,sizeof dist);
    queue<tuple<int,int,int>> qu;
    dist[sx][sy][0] = 0;
    qu.push({sx,sy,0});
    while(!qu.empty()) {
        auto [x,y,z] = qu.front();
        qu.pop();
        if(z == 0) {
            if(a[x][y] > k) {
                dist[x][y][1] = dist[x][y][0];
                z = 1;
            }
        }
        for(int i=0; i<4; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && a[xx][yy] != -1) {
                if(dist[xx][yy][z] > dist[x][y][z] + 1) {
                    dist[xx][yy][z] = dist[x][y][z] + 1;
                    qu.push({xx,yy,z});
                }
            }
        }
    } 
    if(dist[ex][ey][1] == 0x3f3f3f3f) puts("-1");
    else cout<<dist[ex][ey][1]<<"\n";
}

int main() {
    cin >> n >> m >> k;
    cin >> sx >> sy >> ex >> ey;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) scanf("%d",&a[i][j]);
    }
    bfs();
    return 0;
}

https://ac.nowcoder.com/acm/contest/38711/G
双端队列广搜！
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
inline int read()
{
    int x = 0;
    char c =getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48),c = getchar();
    return x;
}

int n,m;
const int N = 2e3 + 9;
char s[N][N];
int dist[N][N];
const int dx[] = {1,-1,0,0},dy[] = {0,0,1,-1};
void solve1()
{
    n = read(),m = read();
    for(int i=1; i<=n; i++) scanf("%s",s[i] + 1);
    deque<PII> qu;
    qu.push_front({1,1});
    memset(dist,0x3f,sizeof dist);
    dist[1][1] = 0;
    while(!qu.empty())
    {
        auto t = qu.front();
        qu.pop_front();
        for(int i=0; i<4; i++)
        {
            int xx = t.first + dx[i];
            int yy = t.second + dy[i];
            if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && s[xx][yy] != '#')
            {
                int d = (s[xx][yy] == '*' ? 0 : 1);
                if(dist[xx][yy] > dist[t.first][t.second] + d)
                {
                    dist[xx][yy] = dist[t.first][t.second] + d;
                    if(d == 0) qu.push_front({xx,yy});
                    else qu.push_back({xx,yy});
                }
            }
        }
    }
    int ans = (dist[n][m] == 0x3f3f3f3f) ? -1 : dist[n][m];
    cout<<ans<<"\n";
}

int main()
{
//    int _ = read();
//    while(_--)
        solve1();
    return 0;
}