[USACO07OCT]障碍路线Obstacle Course题解

题解"/>

[USACO07OCT]障碍路线Obstacle Course题解

题目链接：

洛谷p1649
bzoj1644

发一个不一样的题解

算法:

标签是spfa或DP，有的人用spfa，有的人用bfs，有的人用dfs，可我用的居然是用双端队列优化的Dijkstra。

思路：

这一题可以看成一个最短路。对于某个点，它有四种状态，面对前、后、左、右，所以我们可以把一个点分成四个点。

由于我们要求的不是最要需要多少步，而是最要需要拐多少弯，所以边权有两种，0(不拐弯)和1(拐弯)。此时，用普通的bfs就不行了，可以改成spfa。(平均时间复杂度：k·n²,k为小常数，最坏可达n²)。

用spfa算法会使一个点被扩张多次，使效率降低。但最短路还有另一个更高效的Dijkstra算法。朴素的Dijkstra算法是点数的平方，一般可以加堆优化。但堆优化会增加一个log，在这一题会得不偿失(平均时间复杂度：n²logn²，logn²为堆的时间)。

不过，这一题的边权不是为零就是一，并不要用堆，用双端队列就行。在普通bfs队列里，按层扩张，层数只有两层，正在扩张层和扩张层的下一层，而且正在扩张层在队列中全部在下一层的前面。如果改成双端队列，边权为零说明新扩张的结点和扩张它的结点在同一层，从队头入队；否则，从队尾入队。这样，当一个点第一次被取出时，它离起点的距离就它离起点的最短路。(平均时间复杂度：n²)

code:

双端队列Dijkstra:

#include<queue>
#include<cstring>
#include<iostream>
using namespace std;
const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};//四个方向
char a[110][110];//原地图
int v[110][110][4];//拆点后的单源最短路
bool b[110][110][4];//记录是否被取出
struct node{int x,y,f;
};
deque<node>q;//STL中的双端队列
int main()
{memset(v,0x3f,sizeof(v));//最短路初值为infint n,sx,sy,tx,ty;scanf("%d",&n);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){cin>>a[i][j];if(a[i][j]=='A')//起点{sx=i;sy=j;}else if(a[i][j]=='B')//终点{a[i][j]='.';tx=i;ty=j;}}for(int k=0;k<4;k++)//将起点入队q.push_back((node){sx,sy,k}),v[sx][sy][k]=0;while(!q.empty())//dijkstra{node x=q.front();q.pop_front();if(x.x==tx&&x.y==ty)//终点被取出，得到答案{printf("%d\n",v[x.x][x.y][x.f]);return 0;}if(b[x.x][x.y][x.f])continue;//被取出过，continueb[x.x][x.y][x.f]=1;for(int i=0;i<4;i++)//枚举四个方向{int x1=x.x+dx[i],y1=x.y+dy[i];if(a[x1][y1]=='.'/*越界即为空字符*/&&v[x.x][x.y][x.f]+(x.f!=i)<v[x1][y1][i]){v[x1][y1][i]=v[x.x][x.y][x.f]+(i!=x.f);if(i==x.f)q.push_front((node){x1,y1,i});//边权为零,从队头入队。else q.push_back((node){x1,y1,i});//否则，从队尾入队}}}puts("-1");//终点从未被取出，判断无解
}