自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 22:01:17，当前版本为作者最后更新于2019-01-31 23:21:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

双权图，明显的双端队列BFS啊，题解里怎么没人写呢。。

这里简单介绍一下双端队列BFS吧：

我们在用$\text{dijkstra}$跑最短路的时候，会用到堆优化，把当前最短路最小的点放到前面去。
现在这个图的权要么是$0$，要么是$1$，如果还用堆来维护，似乎有些浪费了。

这个时候我们就要用到双端队列，它支持查询队头、队尾，加入元素到队头、队尾。
我们仍然希望距离大的点放后面，小的放前面，该怎么办呢？
因为只有$0$和$1$两种权值，如果$u\rightarrow v$的边是$0$权，那就把$v$放在队头；否则放在队尾。
现在原本$\Theta(\log n)$的堆优化，在这里只需要$\Theta(1)$了！

介绍完了双端队列BFS，那这题的做法就很明显了，直接套板子即可。
为了方便，这里我直接用了STL，需要使用库$\text{deque}$。
这样做的复杂度是$\Theta(nm)$的，在构造数据+大数据量的情况下，比$\text{SPFA}$和$\text{dijkstra}$ $\color{red}\text{都要快}$。
一些关键的部分我加了注释，没太明白的可以看看。

代码奉上：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<deque>
#include<vector>
#define N 503
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;

struct node{
    int x,y;
    node(int x=0,int y=0):x(x),y(y){}
};

char a[N][N];
bool vis[N][N];
int d[N][N];
const int dx[4] = {0,0,1,-1};
const int dy[4] = {1,-1,0,0};
int n,m,x1,y1,x2,y2;

inline void read(int &x);
void print(int x);
void bfs();

int main(){
    while(1){
        read(n),read(m);
        if(n==0&&m==0) break;
        for(int i=1;i<=n;++i){
            int j = 0;
            char c = getchar();
            while(c!='#'&&c!='@') c = getchar(); 
            while(c=='#'||c=='@'){
                a[i][++j] = c;
                c = getchar();
            }
        }
        read(x1),read(y1),read(x2),read(y2);
        ++x1,++y1,++x2,++y2;
        bfs();
        print(d[x2][y2]);
        putchar('\n');
    }
    return 0;
}

void bfs(){
    int x,y,nx,ny,w;
    memset(d,inf,sizeof(d));
    memset(vis,0,sizeof(vis));
    d[x1][y1] = 0;
    deque<node> q; //新建一只双端队列
    q.push_back(node(x1,y1));
    while(!q.empty()){
        x = q.front().x;
        y = q.front().y;
        q.pop_front();
        if(vis[x][y]) continue; //由于是bfs,所以要判断有没有来过,来过了就不用再来了
        vis[x][y] = true;
        for(int i=0;i<4;++i){ //遍历周围格子
            nx = x+dx[i];
            ny = y+dy[i];
            if(nx>n||nx<1||ny>m||ny<1) continue; //判断是否越界
            w = a[nx][ny]!=a[x][y]; //确定边权,一样为1,不一样为0
            if(d[x][y]+w>=d[nx][ny]) continue; //松弛操作
            d[nx][ny] = d[x][y]+w;
            if(w==0) q.push_front(node(nx,ny)); //0权放前面
            else q.push_back(node(nx,ny)); //1权放后面
        }
    }
}

inline void read(int &x){
    x = 0;
    char c = getchar();
    while(c<'0'||c>'9') c = getchar();
    while(c>='0'&&c<='9'){
        x = (x<<3)+(x<<1)+(c^48);
        c = getchar();
    } 
}

void print(int x){
    if(x>9) print(x/10);
    putchar(x%10+'0');
}

最后再推荐一道双端队列BFS的例题：
[BalticOI 2011 Day1] Switch the Lamp On