训练二：广度优先搜索

题意：有人想乘电梯从a楼到达b楼，电梯只有两种情况，上和下，给定电梯的上下固定楼，求从a到达b的最少移动次数？ -来源HDU1548。

每层电梯有一个数字表示该层可以移动的层数

代码：

#include
#include
#include
#define N 201
using namespace std;
int xx[N],v[N];
int n,a,b;
struct node
{
int step;
int floor;
};
void BFS()
{
node x,y;
queueq;
x.step=0;
x.floor=a;
q.push(x);
v[a]=1;
while(!q.empty())
{
x=q.front();
q.pop();
if(x.floor==b)
{
cout< return;
}
y.floor=x.floor+xx[x.floor];
y.step=x.step+1;
if(y.floor>0&&y.floor<=n&&!v[y.floor])
{
v[y.floor]=1;
q.push(y);
}
y.floor=x.floor-xx[x.floor];
y.step=x.step+1;
if(y.floor>0&&y.floor<=n&&!v[y.floor])
{
v[y.floor]=1;
q.push(y);
}
}
cout<<-1< }
int main()
{
int i;
while(cin>>n>>a>>b&&(n||a||b))
{
memset(v,0,sizeof(v));
for(i=1;i<=n;i++)
{
cin>>xx[i];
}
BFS();
}
return 0;
}

思路：BFS 用队列，用一个数组标记是否到过该层

例2 hdu 1372

象棋里的马从a到达b的最小步数 -来源HDU1372

代码：
 

#include
#include
#include
#define N 10
using namespace std;
char map[N][N];
int v[N][N];
int dic[8][2]={1,-2, 2,1, 1,2, -1,-2, -2,1, -2,-1, -1,2, 2,-1};
char q,w,e,r;
int a,s,d,f;
struct node
{
int step;
int n;
int m;
};
void BFS()
{
node x,y;
int i;
queuep;
x.step=0;
x.n=a;
x.m=s;
p.push(x);
v[a][s]=1;
while(!p.empty())
{
x=p.front();
p.pop();
if(x.n==d&&x.m==f)
{
cout<<"To get from ";
cout<

思路 BFS 队列 注意马有八个方向