本文主要是介绍bzoj 1644: Obstacle Course 障碍训练课 BFS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Description
考虑一个 N x N (1 <= N <= 100)的有1个个方格组成的正方形牧场。有些方格是奶牛们不能踏上的，它们被标记为了'x'。例如下图：
. . B x .
. x x A .
. . . x .
. x . . .
. . x . .
贝茜发现自己恰好在点A处，她想去B处的盐块舔盐。缓慢而且笨拙的动物，比如奶牛，十分讨厌转弯。尽管如此，当然在必要的时候她们还是会转弯的。对于一个给定的牧场，请你计算从A到B最少的转弯次数。开始的时候，贝茜可以使面对任意一个方向。贝茜知道她一定可以到达。
Input
第 1行: 一个整数 N 行
2..N + 1: 行 i+1 有 N 个字符 ('.', 'x', 'A', 'B')，表示每个点的状态。
Output
行 1: 一个整数，最少的转弯次数。
其实这是一道代码能力题，由于路径长度为1，所以我们可以直接bfs（其实是懒）。
对于普通的bfs，我们是将dis[x][y]表示到达(x,y)的最短路，这里我们只需要多加一维，表示到达(x,y)且方向为f的最短路径。一开始我们将起点的四个方向入队，在bfs过程中，枚举四个方向，如果下一步的方向和现在方向相同则距离为0，如果不同距离为1。最后终点的dis的四个方向的最小值即为答案了。
下附AC代码。
#include<iostream>
#include<stdio.h>
#include<queue>
#include<string.h>
#define maxn 105
using namespace std;
struct nod
{int x,y,f;nod(int a,int b,int c){x=a;y=b;f=c;}nod(){}
};
int sx,sy,ex,ey;
int n,m;
char dic[maxn][maxn];
int dis[maxn][maxn][5];
int fx[10]={0,1,-1,0,0};
int fy[10]={0,0,0,1,-1};
queue<nod> q;
int main()
{cin>>n;m=n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){cin>>dic[i][j];if(dic[i][j]=='A'){sx=i;sy=j;}if(dic[i][j]=='B'){ex=i;ey=j;}}memset(dis,0x3f,sizeof(dis));dis[sx][sy][3]=0;dis[sx][sy][1]=0;dis[sx][sy][2]=0;dis[sx][sy][4]=0;for(int i=1;i<=4;i++){q.push(nod(sx,sy,i));}while(!q.empty()){nod now=q.front(); q.pop();for(int i=1;i<=4;i++){int nx=now.x+fx[i],ny=now.y+fy[i];int d;if(now.f==i) d=0;else d=1;if(1<=nx && nx<=n && 1<=ny && ny<=m){if(dic[nx][ny]!='x'){if(dis[nx][ny][i]>dis[now.x][now.y][now.f]+d){dis[nx][ny][i]=dis[now.x][now.y][now.f]+d;q.push(nod(nx,ny,i));}}}}}int ans=987654321;for(int i=1;i<=4;i++)ans=min(ans,dis[ex][ey][i]);printf("%d\n",ans);}
这篇关于bzoj 1644: Obstacle Course 障碍训练课 BFS的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
