广度优先搜索算法(英语:Breadth-First Search,缩写为BFS),又译作宽度优先搜索,或横向优先搜索,是一种图形搜索算法。简单的说,BFS是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。广度优先搜索的实现一般采用open-closed表。
BFS是一种暴力搜索算法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能地址,彻底地搜索整张图,直到找到结果为止。
#include <iostream>
#include <queue>
using namespace std;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int m[100][100],v[100][100];
struct road{
int x;
int y;
int step;
};
queue<road> ma;
int main(){
int a,b;
cin >> a >> b;
int nu;
for(int i=1;i<=a;i++) for(int j=1;j<=b;j++) {cin >> nu;m[i][j]=nu+1;}
int startx,starty,endx,endy;
cin >> startx >> starty >> endx >> endy;
road start;
start.x=startx;
start.y=starty;
start.step=0;
ma.push(start);
v[startx][starty]=1;
bool flag=0;
while(!ma.empty()){
road next;
start=ma.front();
if(start.x==endx&&start.y==endy){cout << start.step << endl;flag=1;break;}
for(int k=0;k<4;k++){
next.x=start.x+dx[k];
next.y=start.y+dy[k];
next.step=start.step+1;
if(m[next.x][next.y]==1&&v[next.x][next.y]==0){
printf("I got %d %dn",next.x,next.y);
ma.push(next);
v[next.x][next.y]=1;
}
}
ma.pop();
}
if(flag==0) cout << "Not Found" << endl;
return 0;
}
コメント