简单的BFS学习笔记

时间:2022-07-23 16:40:35

什么是BFS传送门

今天学习BFS,加油!

先定义个数组:

struct Node{
int a=0;
int b=0;
int step=0;
};
int map[5][4]={//地图
0,0,3,2,//2是终点 3是山,不能走
0,0,0,0,//求从(0,0)出发到2位置的最短路径
0,0,3,0,
0,3,0,0,
0,0,0,3,
}; Node queue[25];  //队列

BFS关键的是队列。

下面写个函数用于入队操作:

int rudui(int a,int b)//入队
{
if(a>=5 || a<0 || b>=4 || b<0 )
{
return 0;
}
//边界控制
if(book[a][b]==0 && map[a][b]!=3)//可以入队
{
queue[tail].a=a;
queue[tail].b=b;
queue[tail].step=queue[head].step+1; book[a][b]=1;//标记下 不能走了
tail++;
} if(map[a][b]==2)
{
return 1;
} return 0;
}

有了以上工具,我们开始工作:

int main()
{
while(head<tail)
{
if( rudui(queue[head].a+1,queue[head].b) || //走上
rudui(queue[head].a,queue[head].b+1) || //走右
rudui(queue[head].a-1,queue[head].b) || //走下
rudui(queue[head].a,queue[head].b-1) ) //走左
{
cout<<"findOK"<<" "<<queue[tail-1].step; //输出路径
return 0;
}
else{
head++; }
} return 0;
}

  OK了。

下面给出完整代码:

#include<iostream>
//#include<queue>
#include<math.h>
using namespace std;
struct Node{
int a=0;
int b=0;
int step=0;
};
int map[5][4]={
0,0,3,2,
0,0,0,0,
0,0,3,0,
0,3,0,0,
0,0,0,3,
}; int book[5][4]={0}; Node queue[25]; int head=0,tail=1;
int rudui(int a,int b)//入队
{
if(a>=5 || a<0 || b>=4 || b<0 )
{
return 0;
}
//边界控制
if(book[a][b]==0 && map[a][b]!=3)//可以入队
{
queue[tail].a=a;
queue[tail].b=b;
queue[tail].step=queue[head].step+1; book[a][b]=1;//标记下 不能走了
tail++;
} if(map[a][b]==2)
{
return 1;
} return 0;
} int main()
{
while(head<tail)
{
if( rudui(queue[head].a+1,queue[head].b) || //走上
rudui(queue[head].a,queue[head].b+1) || //走右
rudui(queue[head].a-1,queue[head].b) || //走下
rudui(queue[head].a,queue[head].b-1) ) //走左
{
cout<<"findOK"<<" "<<queue[tail-1].step; //输出路径
return 0;
}
else{
head++; }
} return 0;
}

  

2015-03-24 15:47:29