發(fā)現(xiàn)這個(gè)東西在特定情況下是非常有用的，所以記錄一下子。

只討論最短路時(shí)的應(yīng)用，但是這個(gè)東西明顯不局限于最短路，可以抽象的模型都是可以的。

定義

這個(gè)東西同樣叫作雙端隊(duì)列 bfs，顧名思義，這種 bfs 里邊使用的是一個(gè)雙端隊(duì)列。

在一張邊權(quán)都是 1 的圖上搞最短路，如果我們使用雙端隊(duì)列 bfs 的話，很明顯我的每個(gè)狀態(tài)在第一次被訪問并且入隊(duì)的時(shí)候就是它的最短路了，這個(gè)東西我們很容易做到 \(O(n)\) 級(jí)別，然而如果邊權(quán)是 \(0/1\) 呢？

我們把邊權(quán)為 0 擴(kuò)展到的點(diǎn)放到前邊， 邊權(quán)為 1 擴(kuò)展到的點(diǎn)放到后邊，這個(gè)樣子前邊的一定就是答案，避免的重復(fù)訪問，這個(gè)東西的復(fù)雜度就非常優(yōu)秀。

例題

對(duì)于一艘在一片巨大的水域上的船來說，水流可能非常危險(xiǎn)，但如果仔細(xì)規(guī)劃路線，它們也可以成為船只前往終點(diǎn)的動(dòng)力。你的任務(wù)就是幫助規(guī)劃路線。

在湖面上每個(gè)點(diǎn)都有一個(gè)水流方向，你可以選擇向水流方向移動(dòng)一個(gè)單位，不用花費(fèi)能量，或是向其他方向移動(dòng)一個(gè)單位，花費(fèi) \(1\) 單位的能量。船只能向以下八個(gè)方向移動(dòng)：東、南、西、北、東南、東北、西南、西北。船只不可以離開海面的邊界。

你需要制定一個(gè)策略，以最少的能量消耗到達(dá)目的地。

給定兩個(gè)整數(shù) \(n,m\) 和一個(gè) \(n\times m\) 的矩陣表示湖面。

有 \(q\) 次詢問，每次詢問給出四個(gè)數(shù) \(r_s,c_s,r_d,c_d\)，求從 \((r_s,c_s)\) 移動(dòng)到 \((r_d,c_d)\) 至少需要多少點(diǎn)能量。

\(1\le n,m\le 10^3,1\le q\le 50\)。

湖面用一個(gè)矩形網(wǎng)格來表示，第一行包含兩個(gè)整數(shù) \(r,c\)，表示該網(wǎng)格的行數(shù)和列數(shù)，\(r,c\le 1000\)。

第 \(2\) 到 第 \(r+1\) 行，每行包含 \(c\) 個(gè)在 \([0,7]\) 之間的整數(shù)字符，表示湖面。字符 \(\texttt{0}\) 表示水流向北，字符 \(\texttt{1}\) 表示向東北，\(\texttt{2}\) 表示向東，依此類推，按順時(shí)針方向排列。

具體方向如下所示（* 表示當(dāng)前所在的位置）：

7 0 1
 \|/
6-*-2
 /|\
5 4 3

第 \(r+2\) 行包含一個(gè)整數(shù) \(n\)，表示將要航行的次數(shù)，\(n\le 50\)。

接下來 \(n\) 行，每行包含四個(gè)整數(shù) \(r_s,c_s,r_d,c_d\)，表示一次從 \((r_s,c_s)\) 到 \((r_d,c_d)\) 的航行。湖面下標(biāo)從 \(1\) 開始。

對(duì)于每個(gè)詢問，輸出一行一個(gè)整數(shù)，表示至少需要的能量消耗。

這個(gè)東西沒啥說的，就直接打板子就行了。

代碼↓

#include <bits/stdc++.h>
using namespace std;
const int MN=1145;
int a[MN][MN], n, m;
int vis[MN][MN], dis[MN][MN];
int sx, sy, ex, ey, Q;
int dx[8]={-1,-1,0,1,1,1,0,-1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
void bfs(){
	memset(vis,false,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	deque <pair<int,int>> q;
	while(!q.empty()) q.pop_front();
	dis[sx][sy]=0; q.push_front({sx,sy});
	while(!q.empty()){
		int x=q.front().first, y=q.front().second; q.pop_front();
		if(vis[x][y]) continue; vis[x][y]=true;
		for(int k=0; k<8; ++k){
			int nx=x+dx[k], ny=y+dy[k];
			if(nx<1||ny<1||nx>n||ny>m) continue;
			int flag=false;
			if(a[x][y]!=k) flag=true;
			if(dis[nx][ny]>dis[x][y]+flag){
				dis[nx][ny]=dis[x][y]+flag;
				if(flag==0) q.push_front({nx,ny});
				else q.push_back({nx,ny});
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n>>m;
	for(int i=1; i<=n; ++i){
		for(int j=1; j<=m; ++j){
			char c; cin>>c;
			a[i][j]=c-'0';
		}
	}
	cin>>Q; while(Q--){
		cin>>sx>>sy>>ex>>ey;
		bfs(); cout<<dis[ex][ey]<<'\n';
	}
	return 0;
}