什么是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