0-1BFS（双端队列BFS）

zhujio / 2023-08-08 / 原文

OIWIKI上面的解释

[ABC176D] Wizard in Maze------------------------------------------------------模板题

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N = 1e3 + 5;

struct Node{
    int x, y;
};

deque<Node>q;

int n, m, ex, ey, sx, sy, dist[N][N];
int dir[4][2]={1,0,0,1,-1,0,0,-1};
char a[N][N];

void bfs(){
    q.push_back({sx, sy});
    dist[sx][sy] = 0;
    while(!q.empty()){
        auto [x, y] = q.front();
        q.pop_front();
        int now = dist[x][y];
        for(int i = 0 ; i < 4; i++){
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] != '#'){
                if(now < dist[nx][ny]){
                    dist[nx][ny] = now;
                    q.push_front({nx, ny});
                }
            }
        }
        for(int i = -2; i <= 2; i++){
            for(int j = -2; j <= 2; j++){
                int nx = x + i;
                int ny = y + j;
                if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] != '#'){
                    if(now + 1 < dist[nx][ny]){
                        dist[nx][ny] = now + 1;
                        q.push_back({nx, ny});
                    }
                }
            }
        }
    }
}


int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n >> m >> sx >> sy >> ex >> ey;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> a[i][j];
        }
    }
    memset(dist, 127, sizeof(dist));
    bfs();
    if(dist[ex][ey] < 1 << 30)cout << dist[ex][ey];
    else cout << -1;
    return 0;
}