《算法竞赛进阶指南》0x26广搜变形

双端队列BFS

在最基本的广度优先搜索中，每次沿着分支的扩展都被记为“一步”。我们通过逐层搜索，解决了从起始状态到每个状态的最小步数问题。这其实等价于在一张边权均为1的图上执行广度优先遍历，求出每个点相对于起点的最短距离。，每个状态在第一次被访问并入队时，计算出的步数即为所求。
如果图上的边权不全为1呢，我们先来讨论边权要么是1，要么是0的情况。

例题
acwing175.电路维修

将每个格点看作无向图上的节点。若两个节点x和y是某个小方格的两个对角，则在x和y之间连边。若方格中的标准件与x到y的线段重合，则边权为0，反之为1。

双端队列主要解决图中边的权值只有0或者1的最短路问题
操作：
每次从队头取出元素，并进行拓展其他元素时

1、若拓展某一元素的边权是0，则将该元素插入到队头
2、若拓展某一元素的边权是1，则将该元素插入到队尾

#include<iostream>
#include<cstring>
#include<deque>
using namespace std;
typedef pair<int,int> PII;
#define N 500
#define endl '\n'
char arr[N+5][N+5];
int t,r,c;
bool v[N+5][N+5];
int dist[N+5][N+5];
int dx[4]={-1,-1,1,1},dy[4]={-1,1,-1,1};
int di[4]={-1,-1,0,0},dj[4]={-1,0,-1,0};
char match[5]="\\//\\";
bool check(int a,int b)
{return ~a&&~b&&a<=r&&b<=c;
}
int bfs()
{memset(dist,0x3f,sizeof dist);memset(v,false,sizeof v);deque<PII>q;q.push_back({0,0});dist[0][0]=0;while(q.size()){PII t=q.front();q.pop_front();int x=t.first,y=t.second;if(x==r&&y==c)return dist[x][y];if(v[x][y])continue;v[x][y]=1;for(int i=0;i<4;i++){int a=x+dx[i],b=y+dy[i];if(!check(a,b))continue;int ga=x+di[i],gb=y+dj[i];int w=0;if(arr[ga][gb]!=match[i])w=1;if(dist[a][b]>w+dist[x][y]){dist[a][b]=w+dist[x][y];if(!w)q.push_front({a,b});else q.push_back({a,b});}}}return -1;
}
int main()
{cin>>t;while(t--){cin>>r>>c;for(int i=0;i<r;i++)cin>>arr[i];if(r+c &1)cout<<"NO SOLUTION"<<endl;else cout<<bfs()<<endl;}return 0;
}

优先队列BFS

对于更加普适性的情况，也就是每次扩展都有各自不同的代价是，求初始状态到每个状态的最小代价，我们有两个解决方案。
1.仍然使用一般的广搜，一般的队列。
不能保证每个状态第一次入队时就能得到最小代价，所以只能允许一个状态被多次更新、多次进出队列，不断搜索，直到队列为空。
2.改用优先队列进行广搜。
每次取出当前代价最小的状态进行扩展沿着各条分支把新状态加入优先队列，不断执行搜索，直到队列为空。
在优先队列BFS，每个状态会被多次更新，多次进出队列，一个状态能以不同的代价在队列中同时存在。不过当每个状态第一次在队列中被取出时就得到了从起始状态到该状态的最小代价，之后再被取出时可以忽略，不再拓展。

总结
1.问题只计最小步数，等价于在边权都为1的图上求最短路。
使用普通的BFS，时间复杂度为$O(n)$。
每个状态只访问（入队）一次，第一次入队时即为该状态的最少步数。
2.问题每次扩展的代价可能是0和1，等价于在边权只有0和1的图上求最短路。
使用双端队列BFS，时间复杂度为$O(n)$。
每个状态更新（入队）多次，只扩展一次，第一次出队时即为该状态的最小代价。
3.问题每次扩展的代价可能是任意数值，等价于一般的最短路问题。
（1）使用优先队列BFS，时间复杂度为$O(nlogn)$。
每个状态更新（入队）多次，只扩展一次，第一次出队时即为该状态的最小代价。
（2）使用迭代思想+普通的BFS，时间复杂度为$O(n^2)$。
每个状态更新（入队）多次，扩展（出队）多次，最终完成搜索后，记录数组中保存了最小代价。

例题
acwing176.装满的油箱

我们使用二元组（city，fuel）表示每个状态，city为城市编号，fuel为剩余油量，并使用记录数组d[city][fuel]存储最小花费。
对于每个问题单独进行一边BFS，每个状态（city，fuel）的分支有：
1.若fuel<C,可以加1升油，扩展到新状态（city，fuel+1）花费在城市加1升油的钱；
2.对于每条从city出发的边（city，next），若边权w不超过fuel，可以开车前往next，扩展到新状态（next，fuel-w）。
我们不断取出优先队列中“当前花费最少”的状态进行扩展，更新扩展到的新状态在d中存储的值，直到终点T的某个状态第一次被去除，即可中止BFS，输出答案。

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
struct Data{int val,id,c;bool operator<(const Data&t)const{return val>t.val;}
};
#define N 1000
#define M 10000
#define C 100
int n,m;
int head[N+5],ne[M*2+5],e[M*2+5],w[M*2+5];
int p[N+5];
bool v[N+5][C+5];
int dist[N+5][C+5];
int tot=0;
void add(int a,int b,int c)
{e[++tot]=b;w[tot]=c;ne[tot]=head[a];head[a]=tot;
}
int dijkstra(int c,int start,int end)
{priority_queue<Data>heap;memset(v,false,sizeof v);memset(dist,0x3f,sizeof dist);heap.push({0,start,0});dist[start][0]=0;while(heap.size()){Data t=heap.top();heap.pop();if(t.id==end)return t.val;if(v[t.id][t.c])continue;v[t.id][t.c]=1;if(t.c<c){if(dist[t.id][t.c+1]>t.val+p[t.id]){dist[t.id][t.c+1]=t.val+p[t.id];heap.push({t.val+p[t.id],t.id,t.c+1});}}for(int i=head[t.id];i;i=ne[i]){if(w[i]>t.c)continue;if(dist[e[i]][t.c-w[i]]>t.val){dist[e[i]][t.c-w[i]]=t.val;heap.push({t.val,e[i],t.c-w[i]});}}}return -1;
}
int main()
{cin>>n>>m;for(int i=0;i<n;i++)cin>>p[i];for(int i=0,a,b,c;i<m;i++){cin>>a>>b>>c;add(a,b,c);add(b,a,c);}int t;cin>>t;while(t--){int CC,S,E;cin>>CC>>S>>E;int ans=dijkstra(CC,S,E);if(ans==-1)cout<<"impossible"<<endl;else cout<<ans<<endl;}return 0;
}

双向BFS

以普通的求最少步数的双向BFS为例，我们只需要从起始状态、目标状态分别开始，两边轮流进行，每次各扩展一整层，当两边各有一个状态在记录数组中发生重复时，就说明这两个搜索过程相遇了，可以合并得到起点到终点的最少步骤。

例题
acwing177.噩梦

题解来源
由于是男孩和女孩同时移动，而不是只有一个人移动，所以这题要用双向广搜。
我们在bfs中按时间t从 1开始枚举。
如果男孩和女孩都不能再继续扩展，则跳出枚举。
对于男孩，每次扩展三步，并标记扩展到的格子。
如果某个能扩展的格子被女孩扩展过，那么直接返回现在的时间。
对于女孩，每次扩展一步，并标记扩展到的格子。
如果某个能扩展的格子被男孩扩展过，那么直接返回现在的时间。
对于鬼，由于鬼是无视墙的，所以我们只需要在扩展男孩和女孩的时候，判断下有没有进入鬼的占领范围即可。
题目中已经给出了，在第 k秒后所有与鬼的曼哈顿距离不超过 2 的位置都会被鬼占领我们在第 t 秒扩展的时候，判断被扩展的格子是否与某个鬼的曼哈顿距离小于 2 即可

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<int,int> PII;
#define MAX_N 800
int t,n,m;
char g[MAX_N+5][MAX_N+5];
PII man,girl,ghost[2];
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
int v[MAX_N+5][MAX_N+5];
bool check(int x,int y,int step)
{for(int i=0;i<2;i++)if(abs(x-ghost[i].first)+abs(y-ghost[i].second)<=2*step)return 0;return ~x&&~y&&x<n&&y<m&&g[x][y]!='X';
}
int bfs()
{int cnt=0,step=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(g[i][j]=='M')man={i,j};else if(g[i][j]=='G')girl={i,j};else if(g[i][j]=='Z')ghost[cnt++]={i,j};}}queue<PII>qm,qg;qm.push(man);qg.push(girl);v[man.first][man.second]=1;v[girl.first][girl.second]=2;while(qm.size()||qg.size()){step++;for(int i=0;i<3;i++)for(int j=0,len=qm.size();j<len;j++){PII t=qm.front();qm.pop();if(!check(t.first,t.second,step))continue;for(int k=0;k<4;k++){int x=t.first+dx[k],y=t.second+dy[k];if(!check(x,y,step))continue;if(v[x][y]==2)return step;else if(!v[x][y]){v[x][y]=1;qm.push({x,y});}}}for(int i=0;i<1;i++)for(int j=0,len=qg.size();j<len;j++){PII t=qg.front();qg.pop();if(!check(t.first,t.second,step))continue;for(int k=0;k<4;k++){int x=t.first+dx[k],y=t.second+dy[k];if(!check(x,y,step))continue;if(v[x][y]==1)return step;else if(!v[x][y]){v[x][y]=2;qg.push({x,y});}}}}return -1;
}
int main()
{cin>>t;while(t--){cin>>n>>m;memset(v,0,sizeof v);for(int i=0;i<n;i++)cin>>g[i];cout<<bfs()<<endl;}return 0;
}