话不多说，直接看题：
没有传送带时，我们可以直接BFS，但因为传送带的出现，可能在队列里的元素到起点时间不单调的问题，而BFS本来就是可以看成随着时间推移而产生的情况，于是我们把队列看成优先队列即可。重复位置只选一次。
下面是AC代码：
#include<bits/stdc++.h>
using namespace std;
int r,c,a[1010][1010],rs,cs,rd,cd,vis[1010][1010],t;
char q;
int dir[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
struct node{int x,y,t;
};
deque<node> qq;
void bfs(void){qq.push_front({rs,cs,0});while(!qq.empty()){node ss=qq.front();qq.pop_front();if(ss.x==rd&&ss.y==cd){cout<<ss.t;return;}if(vis[ss.x][ss.y]!=0) continue;vis[ss.x][ss.y]=1;int xx=ss.x+dir[a[ss.x][ss.y]][0];int yy=ss.y+dir[a[ss.x][ss.y]][1];if(vis[xx][yy]==0&&xx>0&&xx<=r&&yy>0&&yy<=c){qq.push_front({xx,yy,ss.t});}for(int i=0;i<=7;i++){int xxx=ss.x+dir[i][0];int yyy=ss.y+dir[i][1];if(xxx<=0||xxx>r||yyy<=0||yyy>c) continue;if(vis[xxx][yyy]==0){qq.push_back({xxx,yyy,ss.t+1});}}}return;
}
int main(){cin>>r>>c;for(int i=1;i<=r;i++){for(int j=1;j<=c;j++){cin>>q;a[i][j]=q-'0';}}cin>>t;while(t--){while(!qq.empty()) qq.pop_back();memset(vis,0,sizeof(vis));scanf("%d%d%d%d",&rs,&cs,&rd,&cd);bfs();cout<<endl;}
}接下来让我们看看今典的0/1BFS
下面是分析：
我们把顺水流当作0的传送带，于是问题跟上一个类似。
但是，因为只存在两个值，我们用双端队列即可（把顺水流放在队列前，正常的放队尾即可，O（1））
下面是AC代码：
#include<bits/stdc++.h>
using namespace std;
int r,c,a[1010][1010],rs,cs,rd,cd,vis[1010][1010],t;
char q;
int dir[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
struct node{int x,y,t;
};
deque<node> qq;
void bfs(void){qq.push_front({rs,cs,0});while(!qq.empty()){node ss=qq.front();qq.pop_front();if(ss.x==rd&&ss.y==cd){cout<<ss.t;return;}if(vis[ss.x][ss.y]!=0) continue;vis[ss.x][ss.y]=1;int xx=ss.x+dir[a[ss.x][ss.y]][0];int yy=ss.y+dir[a[ss.x][ss.y]][1];if(vis[xx][yy]==0&&xx>0&&xx<=r&&yy>0&&yy<=c){qq.push_front({xx,yy,ss.t});}for(int i=0;i<=7;i++){int xxx=ss.x+dir[i][0];int yyy=ss.y+dir[i][1];if(xxx<=0||xxx>r||yyy<=0||yyy>c) continue;if(vis[xxx][yyy]==0){qq.push_back({xxx,yyy,ss.t+1});}}}return;
}
int main(){cin>>r>>c;for(int i=1;i<=r;i++){for(int j=1;j<=c;j++){cin>>q;a[i][j]=q-'0';}}cin>>t;while(t--){while(!qq.empty()) qq.pop_back();memset(vis,0,sizeof(vis));scanf("%d%d%d%d",&rs,&cs,&rd,&cd);bfs();cout<<endl;}
}
